Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VII edycja konkursu programistycznego

FRAKTAL

8-9 kwietnia 2017

czytaj więcej

Badanie czy liczba jest pierwszą

powrót

Zacznijmy od definicji liczby pierwszej. Liczba pierwsza to taka liczba naturalna większa od 1, która dzieli się tylko przez 1 i samą siebie. Oto kilka liczb pierwszych:

{tex}2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ ...{/tex}

 

 

Warto zauważyć, że takich liczb jest nieskończenie wiele.

Aby określić, czy dana liczba jest pierwsza należy zbadać jej dzielniki. Dla zadanej liczby n sprawdzamy kolejne liczby naturalne należące do przedziału:

{tex}[2...\sqrt{n}]{/tex}

Jeśli któraś z tych liczb jest dzielnikiem, oznacza to, że nasza liczba nie jest pierwsza.

Dlaczego wystarczy sprawdzić tylko liczby od 2 do pierwiastka z n ?

Przeanalizujmy kilka przykładów i wypiszmy dzielniki dla następujących liczb: 24, 25 i 31.

{tex}\sqrt{24}\approx 4,9{/tex}

{tex}D_{24}=\{1,\ 2,\ 3,\ 4,\ |4,9|,\ 6,\ 8,\ 12,\ 24\}{/tex}

{tex}\sqrt{25}= 5{/tex}

{tex}D_{25}=\{1,\ \overbrace{5}^{|5|}\ 25\}{/tex}

{tex}\sqrt{31}\approx 5,6{/tex}

{tex}D_{24}=\{1,\ |5,6|,\ 31\}{/tex}

Warto zauważyć, że jeśli liczba n ma dzielniki większe od {tex}1{/tex}, to będzie ich tyle samo po lewej i prawej stronie {tex}\sqrt{n}{/tex}. W przypadku liczb kwadratowych takich jak np. {tex}25{/tex}, pierwiastek z tej liczby będzie jej dzielnikiem.

Wynika to z faktu, że jeśli liczba {tex}d{/tex}jest dzielnikiem liczby {tex}n{/tex} to zachodzi zależność:

{tex}k = n/d\Rightarrow d = n/k{/tex}

np.

{tex}6 = 24/4 \Rightarrow 4 = 24/6{/tex}

Rozwiązanie w C++:

 

/*****************www.algorytm.edu.pl****************/
#include<iostream>
#include<cstdlib>
using namespace std;
 
bool czy_pierwsza(int n)
{
  if(n<2)
    return false; //gdy liczba jest mniejsza niż 2 to nie jest pierwszą
 
  for(int i=2;i*i<=n;i++)
    if(n%i==0)
      return false; //gdy znajdziemy dzielnik, to dana liczba nie jest pierwsza
  return true;
}
 
int main()
{
  int n;
 
  cout<<"Podaj liczbę: ";
  cin>>n;
 
  if(czy_pierwsza(n)) //lub czy_pierwsza(n)==1
    cout<<"Liczba "<<n<<" jest pierwsza"<<endl;
  else
    cout<<"Liczba "<<n<<" nie jest pierwsza"<<endl;
 
  system("pause");
  return 0;
}