/*

    Prikaz prostih brojeva do broja n.

*/

#include <stdio.h>
#include <math.h>       // zbog sqrt()


// Vraca 1 ako je broj prost, inace vraca 0.
// Ova funkcija ima najmanji broj iteracija jer i ide od 2 do sqrt(broj)
int prost_broj(int broj)
{
    int i;

    for(i=2;i<sqrt(broj);i++)
        if(broj % i == 0)
            return 0;   // ako je broj deljiv sa nekim brojem od 2 do korena iz broj, onda nije prost

    return 1;           // broj je prost jer nije deljiv ni sa jednim brojem od 2 do korena iz broj
}


// Vraca 1 ako je broj prost, inace vraca 0.
// Ova funkcija ima vise iteracija od gornje jer je broj/2 > sqrt(broj)
int prost_broj_v1(int broj)
{
    int i;

    for(i=2;i<broj/2;i++)
        if(broj % i == 0)
            return 0;   // ako je broj deljiv sa nekim brojem od 2 do broj/2, onda nije prost

    return 1;           // broj je prost jer nije deljiv ni sa jednim brojem od 2 do broj/2
}


// Vraca 1 ako je broj prost, inace vraca 0.
// Ova funkcija ima najvise iteracija jer je
// broj/2 > broj/2  i   broj > sqrt(broj)
int prost_broj_v2(int broj)
{
    int i;

    for(i=2;i<broj;i++)
        if(broj % i == 0)
            return 0;   // ako je broj deljiv sa nekim brojem od 2 do broj, onda nije prost

    return 1;           // broj je prost jer nije deljiv ni sa jednim brojem od 2 do broj
}



int main(void){

    int i=2, n=1000;

    printf(" Prosti brojevi do %d su: \n\n",n);

    while (i<n){
        if ( prost_broj(i) )
            printf("%4d\t", i);     // ako je broj (i) prost, prikazi ga
        i++;                        // sledeci broj (i)
    }

    printf("\n\n");
    system("PAUSE");
    return 0;
}