Pascal програма “Перевірити чи число просте”

Решето Ератосфена в математиці — простий стародавній алгоритм знаходження всіх простих чисел менших деякого цілого числа n, що був створений давньогрецьким математиком Ератосфеном. Він є попередником сучасного решета Аткіна, швидшого, але і складнішого алгоритму.

Якщо потрібно знайти всі прості числа менші за певне число N, виписуються всі числа від 1 до N2 -1. Потім в цьому ряду вискреслюються всі числа, які діляться на 2,3, 4 і так далі до N. Числа, які залишилися невикресленими після цієї процедури – прості.

Приклад для n = 20

Запишемо натуральні числа від 2 до 20 в рядок:

2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20

Перше число в рядку 2 — просте. Викреслимо всі числа кратні 2 (кожне друге, починаючи з 2² = 4):

2   3  5  7  9  11  13  15  17  19

Наступне невикреслене число 3 — просте. Викреслимо всі числа кратні 3 (кожне третє, починаючи з 3² = 9):

2   3  5  7  11  13  17  19

Наступне невикреслене число 5 — просте. Викреслимо всі числа кратні 5 (кожне п’яте, починаючи з 5² = 25). І т. д.

Необхідно викреслити кратні для всіх простих чисел p, для яких p²<=n. В результаті всі складені числа будуть викреслені, а залишаться всі прості числа. Для n = 20 вже після викреслювання кратних числу 3 всі складені числа виявляються викресленими.

Програма  Перевірка чи число просте

function isprime(n : integer) : boolean;

var

i, j : integer;

begin

if (2 = i) then

isprime := true

else begin

j := round(sqrt(n))+1;

for i := 2 to j do

if (n mod i = 0) then begin

isprime := false;

exit;

end;

isprime := true;

end;

end;

Comments

comments