Eratostenovo sito za odredjivanje svih prostih brojeva manjih od datog broja

Prosti brojevi su često korisni za rešavanje različitih tipova zadataka pa je dobro imati algoritam koji može da za kratko vreme generiše sve takve brojeve manje od neke granice.

Takav algoritam pripisuje se Eratostenu (3 v. p.n.e.) i zove se Eratostenovo sito. Princip je sledeći:
- zapisati sve prirodne brojeve od 2 do gornje granice
- uzeti prvi nezaokružen broj, zaokružiti ga i precrtati sve brojeve koji su njime deljivi
- ponavljati gornji korak dok ne ostane nijedan nezaokružen  i neprecrtan.
- zaokruženi brojevi su rešenje zadatka - prosti manji od date gornje granice

PROGRAM u C-u:

#include <stdio.h>
#include <math.h>

#define MAX 1000

int main()
{
    int a;
    int x[MAX];
    int broj;
    int i;
    scanf("%d", &a);
    for(i=2; i<=a; i++)
        x[i]=1;
    broj = 2;
    while(broj<=sqrt(a))
    {
        for(i=broj*broj; i<=a; i+=broj)
            x[i]=0;
        do
            broj++;
        while(x[broj]==0);
    }
    for(i=2; i<=a; i++)
        if(x[i]==1)
            printf("%d ",i);
    return 0;
}

Napomena: Program radi najviše do broja 1000. Zamenom broja 1000 sa većim brojem (u redu #define MAX 1000) možemo povećati tu gornju granicu.

Rešenje u C++:

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

    int a;

    int broj;

    int i;

    cin >> a;

    int x[a+1];

    for(i=2; i<=a; i++)

        x[i]=1;

    broj = 2;

    while(broj<=sqrt(a))

    {

        for(i=broj*broj; i<=a; i+=broj)

            x[i]=0;

        do

            broj++;

        while(x[broj]==0);

    }

    for(i=2; i<=a; i++)

        if(x[i]==1)

            cout << i << " ";

    return 0;

}