Zasada szukania liczb pierwszych jest następująca:
Tworzymy tablicę wartości logicznych indeksowaną od 2 do n, gdzie n jest limitem, dla jakiego będziemy szukać liczb pierwszych. Tablicę wypełniamy wartościami true. Kolejnym etapem jest wykreślanie liczb, które nie są liczbami pierwszymi poprzez oznaczanie odpowiadających im pól tabeli jako false. Wykreślanie odbywa się w następujący sposób: dla liczb od 2 do k (gdzie k to zaokrąglony w dół do całości pierwiastek kwadratowy z liczby n - limitu) wykreślamy wielokrotności tej liczby z tablicy. Wypisanie liczb pierwszych ogranicza się do wypisania indeksów pól tabeli, których wartość to true.
Opis algorytmu jest trochę zagmatwany, ale po jego przestudiowaniu powinno się rozjaśnić:
#include <stdio.h> #include <iostream> #include <math.h> using namespace std;int main() { int i,zakres; cout << "Jaki zakres mam przeszukac?" << endl; cin >> zakres; cout << endl; bool tablica[zakres]; for (i=2;i<=zakres;i++) { tablica[i] = true; } int limit = sqrt(float(zakres)); for (i=2;i<=limit; i++) { if (tablica[i]!=false) { for (int j=i+1;j<=zakres;j++) { if (j % i==0) { tablica[j]=false; } } } } cout << "Liczby pierwsze z zakresu od 1 do " << zakres << ":" << endl; for (i=2;i<=zakres;i++) { if (tablica[i]!=false) { cout << i << endl; } } }