Kod: Zaznacz cały
//tytuł: Sito Eratostenesa
//treść zadania: Korzystając z algorytmu "Sito Eratostenesa" napisz program, który wyświetli na ekranie wszystkie liczby pierwsze mniejsze od a. Liczbę a określamy samodzielnie.
//dane wejściowe: i=0, l=2, a=0, ile=0
//dane wyjściowe: Wypisane wszystkie liczby pierwsze z przedziału [2;a] i podana ilość tych liczb.
#include<iostream>
using namespace std;
bool tab[10000000];
int Eratostenes(int a) //A[a] <=> a jest liczbą pierwszą
{
int ile = 0;
//dla każdej liczby - jeśli nie została oznaczona jako złożona wykreśl jej wszystkie wielokrotności mniejsze od a
for(int l = 2; l <= a; l++)
if(tab[l] == 0)
{
ile++;
//zaczynamy wykreślać liczby od 2*l, kończymy gdy dana wielokrotność przekracza a
for(int i = 2*l; i <= a; i+=l)
tab[i] = 1;
}
return ile;
}
int main()
{
int a;
cout << "Algorytm znajduje liczby pierwsze mniejsze od a" << endl;
cout << "a = ";
cin >> a;
cout << "Ilosc liczb pierwszych: " << Eratostenes(a) << endl;
for(int i = 2; i <= a; i++)
//jeśli liczba jest pierwsza to ją drukuj
if(!tab[i])
cout << i << endl;
system ("pause");
return 0;
}