Prime Number Algorithm

Question

Can anyone tell me how to implement Sieve of Eratosthenes algorithm in C? I need to generate prime numbers but my algorithm is slow.

My code:

#include <stdio.h>

int prime(long int i)
{
    long int j;
    int state = 1;
    for(j=2;j<i;j++)
    {
        if((i%j)==0){state=0;break;}
    }
    return state;
}

int main()
{
    int t;
    long int m,n,i;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &m,&n);
        for(i=m;i<=n;i++)
        {
            if(i==1){
                //do nothing for 1
            } else{
                if(prime(i))printf("%d\n",i);
            }
        }
    }
    return 0;
}

t is the number of test cases m and n is the range between which prime are to be printed.

Answer 1

You need to create an array of booleans as big as the maximum prime number you want to find. At the beginning it's completely initialized to true.

The ith cell of such array will be true if i is a prime number, or false if it's not.

Start iterating from i=2: it's prime, then set to false any cell with an index multiple of 2. Go to the next prime number (i=3) and do the same. Go to the next prime (it's i=5: i=4 is not prime: array[4] was set to false while processing i=2) and do the same again and again.