Как узнать число простое или нет?

← →
Витёк (2005-12-24 12:32) [0]

Простое число - это число, которое делится только на себя (без остатка).

Например, 1,2,3,5,7,11,13,17,19,23,29,31,37,… и так до бесконечности. . . .

← →
SergP. (2005-12-24 12:49) [1]

Когда-то была подобная ветка...

Самый простой способ, это

... result:=true; for i:=2 to trunc(sqrt(N)) do if (N mod i) =0 then begin result:=false; break; end; ...

Можно в цикле перебирать только нечетные числа, Будет быстрее, но двойку тоже придется включить.

Если есть массив простых чисел до sqrt(N), то достаточно перебрать в цикле только их а не весь диапазон 2..sqrt(N)

и т.д.

← →
Uncle Archi © (2005-12-24 12:50) [2]

Витёк (24.12.05 12:32) [0]

Проверить, делится ли она на числа, начиная с 2 заканчивая Trunc(sqrt(N)) (т.е. корнем из числа).

← →
Uncle Archi © (2005-12-24 12:53) [3]

Когда писал, не видел SergP. (24.12.05 12:49) [1].

← →
Mystic © (2005-12-24 17:38) [4]

Число один не относят к простым.

← →
Aldor_ (2005-12-24 19:06) [5]

Если нужен список простых чисел до некоторого натурального N, лучше воспользоваться решетом Эратосфена (google forever).

> Витёк (24.12.05 12:32)
Простых способов нет, точнее простой, но медленный в [1] и [2]. А быстрых нет. На этом, пока, криптография и держится.

> Aldor_ (24.12.05 19:06)
Задача несколько обратная.

http://algolist.manual.ru/maths/teornum/

Как узнать число простое или нет? Найти похожие ветки