Bazar, 11.12.2016, 05:19
İnformatikanın məktəbdə tədrisi
Baş səhifə Qeydiyyat Giriş
e-mail: informatik-az@mail.ru · RSS
Menyu
Fotoşəkillər
Giriş forması
Sorğu
Müəllim kimi informatika dərslərində tez-tez istifadə edirəm:
Cavabların sayı: 6165
Faydalı keçidlər

  • ict.edu.az
  • ict.az
  • telekommunikasiya.edu.az
  • İnf-math.narod.ru
  • Millibyte.az
  • kayzen.az/blog/informatika
  • alqoritm.ucoz.org
  • mincom.gov.az
  • Facebook-da
    Təqvim
    «  Dekabr 2016  »
    B.e.Ç.a.ÇC.a.CŞB
       1234
    567891011
    12131415161718
    19202122232425
    262728293031
    Təqdimatlar
    Saat
    Statistika

    Onlayn: 1
    Ziyarətçilərin sayı: 1
    Qeydiyyatdan keçənlərin sayı: 0


     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…).


    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;

    }


    Copyright İsaNaida © 2016
    PYTHON 3.4
    ALPLogo
    Elan
    Fəxr edirik


    Bölmələr
    MÜSABİQƏ
    Azərbaycanda İKT
    Axtarış
    Video
    Info-Ko