Liczby pierwsze to takie liczby naturalne większe od 1, które mają dwa dzielniki naturalne - 1 i siebie samą. Liczby większe od 1 niebędące liczbami pierwszymi nazywami liczbami złożonymi.

Przykładowe liczby pierwsze:


Liczby pierwsze bliźniacze

Parę liczb pierwszych p i q, nazywamy bliźniaczymi, gdy zachodzi równość .

Przykładem takich liczb mogą być pary: .


Sprawdzanie czy liczba jest liczbą pierwszą

Aby sprawdzić czy liczba jest pierwsza, należy przeiterować przez kolejne liczby z przedziału .

Przykładowa funkcja w języku C++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

bool czyPierwsza(int liczba) {
	// Jeżeli liczba jest mniejsza bądź równa zwracamy false
	if(liczba <= 1) return false;

	// Sprawdzamy wszystkie liczby naturalne z przedzialu <2, sqrt(n)>
	for(int i = 2; i <= sqrt(liczba); i++) {
		// jeżeli znaleźliśmy dzielnik,
		// liczba nie jest pierwsza,
		// zwracamy fałsz
		if(liczba % i == 0) return false;
	}

	// Jeżeli nie znaleźliśmy żadnego dzielnika,
	// oznacza to że liczba jest pierwsza,
	// zwracamy prawdę
	return true;
}

Przykładowe wywołanie funkcji:

1
2

const bool pierwsza = czyPierwsza(n);
std::cout << "Liczba " << (pierwsza ? "" : "nie ") << "jest pierwsza";
Liczba n Dzielniki n Dane wyjściowe programu
11 1, 11 Liczba jest pierwsza
15 1, 3, 5, 15 Liczba nie jest pierwsza


Sito Erastotenesa

Sito Erastotenesa pozwala nam na szybkie wyznaczanie liczb pierwszych z przedzialu . Strategia nie jest skomplikowana. Wystarczy znajdować kolejne liczby pierwsze i wykreślać jej wielokrotności. Dla przykładu, zaprezentuję przesiewanie liczb od 2 do 16. Na początku tworzymy tablicę wszystkich liczb:

Zaczynamy od wszystkich wielokrotności 2:

To samo robimy dla kolejnej liczby czyli 3:

Po sprawdzeniu pozostałych liczb okazuje się, że wykreśliliśmy już ich wszystkie wielokrotności. Jedyne niewykreślone liczby jakie nam zostały to , czyli liczby pierwsze z zadanego przedziału. Warto napomnieć, że obowiązuje tutaj ta sama zasada co w sprawdzaniu czy liczba jest pierwsza - wystarczy sprawdzać liczby do .

Implementacja algorytmu w języku C++:

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

#include <iostream>
#include <cmath>
using namespace std;

void sito(bool tablica[], int n) {
	// Tablica domyślnie jest wypelniona wartościami false
	// Dla wszystkich liczb >= 2, ustawiamy wartość początkową true
	for(int i = 2; i <= n; i++) {
		tablica[i] = true;
	}
	
	for(int i = 2; i <= sqrt(n); i++) {
		// Jeżeli liczba jest już wykreślona,
		// nie ma potrzebny sprawdzać jej wielokrotności
		// (również będą już wykreślone)
		if(tablica[i] == false) continue;
		
		// Wykreślamy wielokrotności liczby
		for(int j = i * 2; j <= n; j += i) {
			tablica[j] = false;
		}
	}
}

int main() {
	const int n = 100;
	
	// Inicjalizujemy tablicę o wielkości n + 1
	// Dla uproszczenia algorytmu, tablica będzie mieścić liczby od 0 do n
	// Dzięki temu indeks będzie reprezentować liczbę
	bool tablica[n + 1] = {};
	
	// Wywołujemy funkcję przesiewającą tablicę
	sito(tablica, n);
	
	// Wyświetlamy wszystkie liczby pierwsze
	for(int i = 2; i <= n; i++) {
		if(tablica[i]) cout << i << " ";
	}
}