Wstęp:

• DEFINICJA. Liczba pierwsza to taka liczba naturalna, która ma dokładnie dwa dzielniki naturalne: jedynkę i samą siebie.
• Aby określić czy liczba n jest pierwsza, należy sprawdzić jej dzielniki.
• Nie musimy sprawdzać wszystkich dzielników w przedziale <2, n>.
• Wystarczy sprawdzić czy dana liczba n ma dzielniki w przedziale <2, sqrt(n)>, gdzie sqrt-pierwiastek
• Korzystając z poniższej ilustracji z dzielnikami dla przykładowych liczb, przeanalizuj dlaczego tak jest:
  

Film może pomóc:

Schemat algorytmu:

Pobierz plik algorytmu dla programu Magiczne Bloczki

Liczby pierwsze do 100:

Przykładowy kod programu w C++ z wykorzystaniem funkcji opartej o iterację while:

#include <iostream>
using namespace std;
// funkcja zwracająca wartość logiczną 
// true - liczba n jest pierwsza
// false - liczna n nie jest pierwsza
bool czyPierwsza(int n){
	if(n==1) return false;
	int i=2;
	while(i*i<=n){
		if (n%i==0) return false;
		i++;
	}
	return true;	
}
int main() {
	int liczba;
	cout << "podaj liczbe: "; 
	cin >> liczba;
	if(czyPierwsza(liczba)) cout << "\n" << liczba << " jest liczba pierwsza";
	else cout << "\n" << liczba << " NIE jest liczba pierwsza";
	return 0;
}

Inna postać funkcji sprawdzającej pierwszość liczby n z wykorzystaniem iteracji for:

bool czyPierwsza(int n){
	if (n<2) return false;
	for(int i=2; i*i<=n; i++){
		if (n%i==0) return false;
	}
	return true;	
}

Wykorzystanie kodu

• Powyższy kod można wykorzystać w środowisku Dev C++ lub innym. Wystarczy utworzyć nowy projekt i wkleić ten kod zamiast istniejącego.
• Można też użyć kodu na jednej ze stron WWW z kompilatorami on-line, na przykład na stronie: www.cpp.sh