2-15r

Дано натуральное число N. Проверить, является ли оно простым.

Число называется простым, если оно не имеет никаких делителей, кроме 1 и самого числа. Поэтому алгоритм почти ясен: надо проверить делится ли это число на возможные делители и если не делится ни на один возможный делитель – число простое. Из четных чисел, только число 2 является простым, поэтому в строке 6 проверяем, равняется ли число 2, а в строке 8 – четное ли оно. В задаче 2.13 мы отметили, что максимальным делителем у числа n может быть n div 2 (n/2). В примечании к задаче 2.13 мы отметили, что в числе каждый делитель имеет свою пару. Например для числа 1024:

Делитель 2 имеет свою «пару» число 1024 div 2 = 512, а если не делится на 2, значит не делится и на n div 2.

Делитель 4 имеет свою «пару» число 1024 div 4 = 256, а если не делится на 2, значит не делится и на n div 4.

Делитель 8 имеет свою «пару» число 1024 div 8 = 128, а если не делится на 2, значит не делится и на n div 8.

Делитель 16 имеет свою «пару» число 1024 div 16 = 64, а если не делится на 2, значит не делится и на n div 16.

Делитель 32 имеет свою «пару» число 1024 div 32 = 32, а если не делится на 2, значит не делится и на n div 32.

Все пары делителей сошлись в числе 32 (32*32=1024).

Отсюда и алгоритм:

Программа 2.15а. Исходное число n будем проверять делится ли оно на число k= 3, 5, 7 и т.д. до тех пор, пока k*k<=n - строка 11 (Вспомните: число 32 было последним меньшим делителем). И если проверены все возможные делители (обратите внимание: именно только возможные делители – нечетные числа , начиная с 3), и k*k стало больше n, то число простое – строка 12.

Программа 2.15b. В этой программе мы уменьшили количество проверяемых делителей. Вообще самым оптимальным было бы – проверять на деление на простые числа. Например, число 15 не может быть делителем, если делителями не являются простые числа 3 и 5, и зачем проверять на делимость на число 35, если уже проверили на числа 5 и 7? Но у нас нет набора простых чисел. Но у нас есть набор «кандидатов» в простые числа! Это числа вида 6*k +/- 1! (6*k + 1 и 6*k - 1) Удивительно, но все простые числа можно получить по этой формуле ( но не все числа этого вида – простые). При к=1 имеем 5 и 7, при к=2 имеем 11 и 13, при к=3 имеем 17 и 19. Вот так бы и дальше! Но, при к=4 имеем 23 и 25 (не простое, а жаль). Но все равно чисел такого вида меньше, чем всех нечетных. Выпишем эти числа: 5, 7, 11, 13, 17, 19, …Каждое следующее число получается из предыдущего прибавлением 2 или 4 (и они чередуются: прибавляется 2, 4, 2, 4, 2, 4…).

В программе 2.15b ( строка 12) переменная p реализует такое прибавление (сначала p=2, а затем в цикле она вычисляется по формуле p = 6 – p: и получается 2, 4, 2, 4, 2, 4…).

Program A2_15a;

Var

n,k:integer;

begin

readln(n);

if(n=2) then

begin writeln('YES');readln; exit; end;

if(n mod 2 = 0) then

begin writeln('NO');readln; exit; end;

k:=3;

while (k*k<=n) and (n mod k <>0) do k:=k+2;

if (k*k>n) then writeln('YES')

else writeln('NO');

readln;

end.

// Program A2.15a;

#include <iostream>

using namespace std;

int main()

{ int n,k=3;

cin>>n;

if(n==2){cout<<"YES\n"; return 0;}

if(n%2==0 ){cout<<"NO\n"; return 0;}

while(k*k<=n && n%k!=0) k=k+2;

if(k*k>n)cout<<"YES\n";

else cout<<"NO\n";

return 0;

}

Program A2_15b;

Var

n,k,p:integer;

begin

readln(n);

if(n=2) then

begin writeln('YES');readln; exit; end;

if(n mod 2 = 0) or (n mod 3 = 0) then

begin writeln('NO');readln; exit; end;

k:=5; p:=2;

while (k*k<=n) and (n mod k <>0) do

begin k:=k+ p; p:=6-p; end;