1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 26 28 29 30 31 32 33 34 35 36 | Program A2_16a;
Var n,p,k,k1,p1:
integer; begin readln(n); if (n=1)
then begin writeln('n=1 ???'); exit;end; write('2'); if (n<=3)
then exit; write(' 3'); if (n<5)
then exit ; p:=2; k:=5; while
(k<n) do begin if (k mod 3 <>0) then
begin k1:=5; p1:=2; while
(k1*k1<=k) and (k mod k1<>0) do
begin k1:=k1+p1; p1:=6-p1; end; if (k1*k1>k) then write(' ',k); end;
k:=k+p; p:=6-p; end; writeln; readln; | // Program A2.16a;
#include <iostream>
using namespace std;
int main() { int
n,p,k,k1,p1;
cin>>n;
if(n==1){cout<<"n=1 ???\n"; return 0;}
cout<<"2"; if(n<=3)
return 0;
cout<<" 3"; if(n<5)
return 0; for(p=2,
k=5; k<n; k=k+p, p=6-p) { if(k%3!=0)
{ k1=5; p1=2;
while(k1*k1<=k && k%k1!=0)
{k1=k1+p1; p1=6-p1;}
if(k1*k1>k) cout<<" "<<k; } }
cout<<endl; return 0; |
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 58 | Program A2_16b; Var n,p,k: integer;
Function checkprost(n:integer):integer; Var k,p: integer; begin if (n mod 3=0) then checkprost:=0
else begin p:=2; k:=5;
while(k*k<=n) and (n mod k<>0) do begin
k:=k+p; p:=6-p; end; if
(k*k>n) then checkprost:=1 else checkprost:=0; end end;
BEGIN readln(n); if (n=1)
then begin writeln('n=1 ???');readln; exit;end; write('2'); if (n<=3)
then begin readln; exit; end; write(' 3'); if
(n<5) then begin readln; exit; end; p:=2; k:=5; while
(k<n) do begin if
(checkprost(k)=1) then write(' ',k);
k:=k+p; p:=6-p; end; writeln; readln; | // Program A2.16b; #include <iostream>
using namespace std;
int checkprost(int n) { int k=5,p=2;
if(n%3==0)return 0;
while(k*k<=n && n%k!=0){k=k+p; p=6-p;} if(k*k>n)
return 1; else return 0; }
int main() { int n,p,k;
cin>>n;
if(n==1){cout<<"n=1 ???\n"; return 0;}
cout<<"2"; if(n<=3)
return 0;
cout<<" 3"; if(n<5)
return 0; for(p=2,
k=5; k<n; k=k+p, p=6-p) if(checkprost(
k)) cout<<" "<<k;
cout<<endl; return 0; } |
Дано натуральное число N. Найти все простые числа меньшие N.
Научившись в предыдущей задаче проверять число на простоту, решение настоящей задачи становится уже тривиальным. Переберем все «кандидаты» в простые числа и проверим каждый «кандидат» по предыдущему алгоритму. Простые числа 2 и 3 выведем отдельно (если n > 3). Перебирать числа начнем с 5 (по формуле 6*k +/- 1 «кандидаты» в простые числа начинаются с 5).
Программа 2.16b отличается от 2.16a тем, что проверка числа на простоту вынесена в отдельную подпрограмму – функцию (строки 10 – 31). Если число простое, то функция возвращает ( она равна) 1, а если не простое, то 0. В главной программе (строка 53) простое число выводится на экран.
