0

I used the following code to generate a simple sieve-

#include<stdio.h>

int main()
{
int a,b,i,j;
scanf("%d%d",&a,&b);

int m = (a)/2;
int d[m+1];

for (i=0;i<m;i++)
    d[i]=1;

for (i=1;i<=m;i++)
    for (j=i;j<=((m-i)/(2*i+1));j++)
        d[i+j+2*i*j]=0;

if (b<=2) printf("2\n");
for (i=0;i<m;i++)
    if(d[i]!=0&&i!=0) printf("%d\n",2*(i)+1);

}

but I want to eliminate the extra time used for finding primes upto b, for this I made m = (a-b)/2 and tried starting the main for loop from b/2 and sqrt b/2 instead of zero but it doesn't seem to work, how can I reduce the extra calculation ? Thanks in advance.

Naman Jain
  • 63
  • 1
  • 9
  • The sieve must start at 2 or you don't eliminate multiples of 2. You could pre-calculate all primes up to b, but that defeats the purpose. – Garr Godfrey Jun 02 '15 at 08:06
  • possible duplicate: http://stackoverflow.com/questions/453793/which-is-the-fastest-algorithm-to-find-prime-numbers – Garr Godfrey Jun 02 '15 at 08:14

0 Answers0