Wednesday, July 17, 2013

C Program to find all the prime numbers less than or equal to a given integer by Eratosthenes' method

The sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes (below 10 million or so). It is named after Eratosthenes of Cyrene, a Greek mathematician.

Here I am implementing his algorithm in C language to find all the prime numbers less than or equal to a given integer.

To check the algorithm refer: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

PROGRAM WITH COMMENTS

main(){
    int l,i,temp=0,p,t;
    printf("Enter the limit:");
    /*
    GET the limit 'l'
    */
    scanf("%d",&l);
    /*
    Create an array store a list of consecutive integers from 2 to l
    */
    int nlist[l];
    /*
    Store the consecutive integers from 2 to l
    */
    for(i=2;i<=l;i++){
        nlist[temp]=i;
        temp++;
    }
    /*
    Initially, let p equal 2, the first prime number.
    Starting from p, count up in increments of p and mark (here I put 0 for marking) each of these
    numbers greater than p itself in the list.

    Find the first number greater than p in the list that is not marked. If there was no such number, stop.
    Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.

    When the algorithm terminates, all the numbers in the list that are not marked are prime.
    */
    for(i=0;i<temp;i++){
        if(nlist[i]!=0){
            t=i;
            p=nlist[i];
            while((t+p)<temp){
                t=t+p;
                nlist[t]=0;
            }
        }
    }

    /*Printing Prime numbers*/
    for(i=0;i<temp;i++){
        if(nlist[i]!=0)
            printf("%d, ",nlist[i]);
    }
}


PROGRAM WITHOUT COMMENTS

main(){
    int l,i,temp=0,p,t;
    printf("Enter the limit:");    
    scanf("%d",&l);    
    int nlist[l];    
    for(i=2;i<=l;i++){
        nlist[temp]=i;
        temp++;
    }    
    for(i=0;i<temp;i++){
        if(nlist[i]!=0){
            t=i;
            p=nlist[i];
            while((t+p)<temp){
                t=t+p;
                nlist[t]=0;
            }
        }
    }
    for(i=0;i<temp;i++){
        if(nlist[i]!=0)
            printf("%d, ",nlist[i]);
    }
}

No comments:

Post a Comment