iİnformatikanın məktəbdə tədrisi

2-16r

Дано натуральное число N.  Найти все простые числа меньшие N.

Научившись в предыдущей задаче проверять число на простоту, решение настоящей задачи становится уже тривиальным. Переберем все «кандидаты» в простые числа и проверим каждый «кандидат» по предыдущему алгоритму. Простые числа 2 и 3 выведем отдельно (если n > 3). Перебирать числа начнем с 5 (по формуле 6*k +/- 1 «кандидаты» в простые числа начинаются с 5).
Программа 2.16b отличается от 2.16a тем, что проверка числа на простоту вынесена в отдельную подпрограмму – функцию  (строки 10 – 31). Если число простое, то функция возвращает ( она равна) 1, а если не простое, то 0. В главной программе (строка 53) простое число выводится на экран.


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;

 end.                                          		   // 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;

 END.

// 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;

}