Tuesday, 16 December 2014

prime1 spoj

PRIME1 (SPOJ)

in the prime1 question the , the click point was that the range in which we had to print all the prime number was very small in comparison to the overall range of numbers.. So what we did was we found out all the possible prime factor within that range that(10^9) that could be a prime divisor for any number within the overall range...
Now one possibility is that we will compute all the prime numbers present within (10^9) but that is allot of work in comparison to the computing only in given ranges

so we decided to opt for the latter and computed only those prime numbers which were asked for

since the range is 10^5 and over all constraint is 10^9
it would take 10^4 test cases to beat the second method and make the 1st method more effective

Code:

#include <stdio.h>
int main()
{

    unsigned long long a[31625],b[100005],d,e,f,i,j,t,m,n;
    long long c;
    for(i=0;i<100005;i++)
        b[i]=0;
    for(i=0;i<31625;++i)
        a[i]=0;
    for(i=2;i<179;i++)
        if(!a[i])
        for(j=2;j*i<31625;j++)
        a[i*j]=1;

  scanf("%llu",&t);
  while(t--)
  {
      scanf("%llu",&m);
      scanf("%llu",&n);
      for(i=2;i<31625 && i*i<n;i++)
      {     if(!a[i])
          for(j=(m/i)*i;j<=n;j+=i)
          { c=j-m;

          /*if(j==2 || j==3)
            continue;
          if(j==1)b[j]=1;*/

              if(c>=0 && c<100001 && j!=i){
                b[c]=1;
                //printf("%lld\n",c+m);
                }
          }
      }

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

  }

}