Простые числа
Sunny Girl
Профессионал
11/23/2007, 2:20:38 AM
Собсно,вопрос таков.Граждане программисты,помогите.)
Давно забыт мной великий и ужасный Pascal...Ан нет,требуется..
В общем,прошу по возможности подсказать мне алгоритм для проверки числа на простоту.На Pascal.Ибо теоретически и на C его представляю,а вот Pascal..
Давно забыт мной великий и ужасный Pascal...Ан нет,требуется..
В общем,прошу по возможности подсказать мне алгоритм для проверки числа на простоту.На Pascal.Ибо теоретически и на C его представляю,а вот Pascal..
do-do
Мастер
11/23/2007, 10:35:55 AM
а попробуй ПРОСТО теоретически алгоритм написать БЕЗ привязки к языку
P.S. После всех манипуляций найди такой алгоритм зовущийся Решето Эратосфена
А если в поисковике забабахаешь еще слово pascal думаю счастье твое будет безмерно
P.S. После всех манипуляций найди такой алгоритм зовущийся Решето Эратосфена
А если в поисковике забабахаешь еще слово pascal думаю счастье твое будет безмерно
DELETED
Акула пера
11/23/2007, 1:03:19 PM
Решето Аткина рулит! :)
maxdiversexnarod1
Специалист
11/23/2007, 5:34:20 PM
Нафиг решето, тут же нужно одно число проверить на простоту??
Даже тривиальный алгоритм будет быстрее:
var i,n:integer;
prime:boolean;
begin
read (n);
prime := true;
i:=2;
while i*i<=n do
begin
if (n mod i) = 0 then
prime := false;
i := i + 1;
end;
if prime then
write ('prime number')
else
write ('not a prime number');
end.
P.S. Раз уж начали понтоваться тут с алгоритмами, внесу и свои 5 копеек :)
Алгоритм Baillie-Pomerance-Selfridge-Wagstaff рулит!
Работает за O (log N) на встроенных типах данных!
Работает за O (log^3 N) на длинной арифметике!
Покупайте, недорого :)
Даже тривиальный алгоритм будет быстрее:
var i,n:integer;
prime:boolean;
begin
read (n);
prime := true;
i:=2;
while i*i<=n do
begin
if (n mod i) = 0 then
prime := false;
i := i + 1;
end;
if prime then
write ('prime number')
else
write ('not a prime number');
end.
P.S. Раз уж начали понтоваться тут с алгоритмами, внесу и свои 5 копеек :)
Алгоритм Baillie-Pomerance-Selfridge-Wagstaff рулит!
Работает за O (log N) на встроенных типах данных!
Работает за O (log^3 N) на длинной арифметике!
Покупайте, недорого :)
do-do
Мастер
11/23/2007, 6:11:23 PM
(Sunny Girl @ 22.11.2007 - время: 23:20)
В общем,прошу по возможности подсказать мне алгоритм для проверки числа на простоту.
Тут даже семантический анализ не поможет, что ж имел ввиду автор
Одно число иль массив. Если задача учебная, то скорей всего будет предьявлен массив чисел - из которых нужно выбрать простые :)
В общем,прошу по возможности подсказать мне алгоритм для проверки числа на простоту.
Тут даже семантический анализ не поможет, что ж имел ввиду автор
Одно число иль массив. Если задача учебная, то скорей всего будет предьявлен массив чисел - из которых нужно выбрать простые :)
contravene
Новичок
11/28/2007, 10:53:51 PM
(Sunny Girl @ 22.11.2007 - время: 23:20) Ибо теоретически и на C его представляю,а вот Pascal..
Интересно... на С представляешь а на паскале нет???
Я не вижу мега разницы между С и паскалем когда дело доходит до елементарых математических вычислений. (хотя паскаля не видел еще со старших классов в школе)
Уверен, что раз на С ты ее забабахать сможешь - на паскале не будет проблем.
PS: Щас посмотрел на паскалевское := присваивание - как же оно меня бесит ! Хорошо что майкрософт паскаль не стал реализовывать в студии !
Интересно... на С представляешь а на паскале нет???
Я не вижу мега разницы между С и паскалем когда дело доходит до елементарых математических вычислений. (хотя паскаля не видел еще со старших классов в школе)
Уверен, что раз на С ты ее забабахать сможешь - на паскале не будет проблем.
PS: Щас посмотрел на паскалевское := присваивание - как же оно меня бесит ! Хорошо что майкрософт паскаль не стал реализовывать в студии !
do-do
Мастер
11/28/2007, 11:14:42 PM
(contravene @ 28.11.2007 - время: 19:53) Щас посмотрел на паскалевское := присваивание - как же оно меня бесит !
Что сказать :) Язык (Паскаль) первоначально разрабатывался как учебный (эт уже у нас... Стали лепить на нем все шо хошь) И тут было важно ВЫДЕЛИТЬ разницу оператора присваивания := и логического оператора равно =
Что сказать :) Язык (Паскаль) первоначально разрабатывался как учебный (эт уже у нас... Стали лепить на нем все шо хошь) И тут было важно ВЫДЕЛИТЬ разницу оператора присваивания := и логического оператора равно =