BartoIT Blog

Na stronie Centralnej Komisji Egzaminacyjnej ( CKE ) możemy znaleźć wykaz algorytmów, których znajomość jest wymagana. Jednym z nich jest znajomość poprawnego zbadania, czy podana liczba jest liczbą pierwszą. Nie zwlekając dłużej przejdźmy do rozwiązania problemu.
Najpierw trochę teorii o poprawnym poszukiwaniu liczby pierwszej.

Liczba pierwsza to liczba, która dzieli się tylko przez 1 i samą siebie. Tego warunku nie spełnia liczba 1 i 0, z prostych przyczyn definicji liczby pierwszej, która dokładnie brzmi:

 

Liczby pierwsze to liczby naturalne, które posiadają dokładnie dwa dzielniki (liczbę 1 i samą siebie).

Aby wykazać, że liczba naturalna jest liczbą pierwszą musimy wykazać, że reszta z dzielenia liczby przez liczby mniejsze, bądź równe pierwiastkowi kwadratowemu liczby sprawdzanej jest różna od 0.
Wiem – brzmi to trochę zawile. Sam pisząc to powyżej dwa razy się zastanawiałem, czy poprawnie napisałem to co chciałem Ci powiedzieć. Niestety prościej się nie da, gdy nie chcesz pominąć wszystkich warunków do poprawnego wykonania zadania.

Rozwiązanie

Schemat krokowy

1. Podaj liczbę naturalną n.
2. Jeżeli liczba n<2 wypisz „To nie jest liczba pierwsza”
3. w przeciwnym wypadku kontynuuj algorytm
4. Rób dopóki i:=2 ; i *i<=n ; i+1
5. Jeżeli n mod i = 0 wypisz „To nie jest liczba pierwsza”
6. W przeciwnym wypadku
7. Wypisz „To jest liczba pierwsza”

#include<iostream>
#include<cstdlib>
using namespace std;
 
bool czy_pierwsza(int n)
{
  if(n<2)
    return false; //gdy liczba jest mniejsza ni%u017C 2 to nie jest pierwsz%u0105
 
  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 liczbe: ";
  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;
}