UVa - 10852 ( Less Prime Solution )

Try Yourself First. For help Scroll Down .

Clearance :  Now this is an interesting problem . I would like to Suggest you not to see the solution right now and Do a Paper-Pen work . Your Constraints are the Given Prime Number will be Greater than or Equal " p*x " but less than '' (p+1)*x '' where p is an integer and  x is the prime number . Here we have to find out the ' p ' mainly and then ' x ' .

Here ' p ' is 2. The rule is to find the ' x ' is  x = (n/2)+1 .Then print the immediate value greater than or equal to x. This rule you can find out from the samples ... just divide the given sample by two . And then print the result . Use SIEVE to generate the Primes .

Code :


#include<bits/stdc++.h>
#define n 10000

int b[10002];
int primenumber[1300];

void prime()
{
    int i,j,k,l;
    for(i=1;i<=n;i++) {b[i]=1;}
    b[1]=0; l=0;
    for(i=2;i<=sqrt(n);i++)
    {
      if(b[i]!=0)
      {
        for(k=2*i;k<=n;k=k+i)
        if(b[k]!=0)
            b[k]=0;
      }
    }

    for(int i=0; i<n; i++)
    {
        if(b[i]!=0)
            primenumber[l++]=i;
    }
}
int main()
{
  prime();
  int t;
  scanf("%d",&t);
  while(t--)
  {
      int m;
      scanf("%d",&m);
      for(int i=0; i<1229; i++)
      {
           int x = m/2 + 1;
           if(primenumber[i]>=x)
           {
               printf("%d\n",primenumber[i]);
               break;
           }
      }
  }
  return 0;
}

=>  Need Help ?? Leave a Comment .