Дано натуральное число 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…).
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
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;
}
|
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
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;
if
(k*k>n) then writeln('YES')
else writeln('NO');
readln;
end.
|
// Program A2.15b;
#include <iostream>
using namespace std;
int main()
{ int
n,k=5,p=2;
cin>>n;
if(n==2){cout<<"YES\n"; return 0;}
if(n%2==0
|| n%3==0){cout<<"NO\n"; return 0;}
while(k*k<=n && n%k!=0) {k=k+p; p=6-p;}
if(k*k>n)cout<<"YES\n";
else
cout<<"NO\n";
return 0;
}
|