Prime Generator

Brute force doesn't seem to work? Anybody with any pointers?

Just discarding even numbers is not enough for this problem. You might want to look up some sieving techniques for finding prime numbers.

Okay first I got a wrong answer...then eventually it timed out... now my code is now jacked up and very fast but its reading a wrong answer agian lol! No idea why its wrong of course all the answer seem right.

 I am getting the time limit exceeded...

I checked all odd nos from 1 to sqrt(n)

still time limit exceeded...

@Neerav you need a faster algorithm :)

#include<iostream>

using namespace std;

int main

 code copy paste mangal?

lolzz nahi hoga 

 try removing all nos with 5 at their endings, in brute force method, do not check every third no. ... so div by 3 is excluded, wow, this is soo much fun, removing soo many cases yet ot able press into the limited time

my program in java fails compilation...

its running fine on my machine.

Can anyone tell why?

Read the FAQ / Help pages.

Hey I used Sieve of Erathosthenes to get all primes <= sqrt(10^9) and used it to check for primes > sqrt(10^9) it gives me a TLE is there a better way?

There are a lot of primes less than 10^9

Hey I have used what they call as "sieve of erasthosthenes" and have a complexity of log N for any number N, but still timing out!

I tht 10^5 * log(10^9) *10 should fit in the scheme properly??

Any idea y??

ermm....sorry wrongly quoted i used some math theorem....! but i m sure that i use only log N steps(assuming mod takes constant time)

Why the people who have succesfully submitted a solution are not allowed to view other's solutions ????

We learn a lot just by looking at others solution. For instance, my best shot at this problem solves this in 3.6 secs and Mr. Josh has solved this in 0..04 secs!!! Please ponder over this please !!!!!

We will definitely doing this.

For a single test case my program is taking less than 6 seconds but for multiple test cases it takes more time.

So you'll need to make your algorithm a lot faster then :)

hi aewl..i am new hea..can you plz tell me the way to store such big numbers like 10000000000 in c. that even gng out of long range

The largest n can be is less than 2^30, so it will fit inside a normal int perfectly fine.

#include <iostream>
#include <vector>
using namespace std;

int *list = NULL;

int sieve(long p){
   list[0] = 0;
   for(long i = 2; i * i < p; i++){
      if(list[i-1] == 1){
         for(long j = i+i; j <= p; j += i){
            list[j-1] = 0;
         }
      }
   }
return 0;
}

int main(){
   int t;
   vector<long > v;
   long m,n;
   
   cin>>t;
  
   for(int i = 0; i < t; i++)
   {
      cin >> m >> n;
      list = new  int[100000000];
      for(long i = 0; i < n; i++)
         list[i] = 1;
      sieve(n);
      for(long j = m; j <= n; j++){
         if(list[j-1] == 1)
            v.push_back(j);
           
      }
      v.push_back(-1);
      delete [] list;
      list = NULL;
   }
  
   for(long i = 0; i < v.size(); i++){
      if(v.at(i) == -1)
         cout << endl;
      else
         cout << v.at(i) << endl;
   }  
  
   return 0;
}
plzzzzzzz help me

where i am wrong.......

Runtime error (OTHER) almost always means you use too much memory. 100000000 ints is 763mb. That is far too much memory.

Stephen,plzzzzz tell me how to resolve this problem.......

plzzzzzzz buddy help me.....

thankx in advance.....

@mukul:

Simple eratosthenes' sieve would probably not work here.

@mukul

you need to generate primes upto sqrt(10^10) and then for each test case use sieve type method to find numbers of prime in the given range using the prime generated earlier.

I am using seive of eratosthenes but still my program is taking 30sec to go for extreme case ie 999990000-1000000000 can anyone help me

mine is taking 11 secs :(

mine takes less than a second to run the worst case 999900000 to 1000000000.

is that not good enough?

is the program supposed to run all test cases in the given limit or is the limit for each test case?

i tried just calculating the primes for the worst case 10 times and it ran in about 2.5 sec .

but when i print them too ,using printf, it takes 11 sec....which means it takes about 8.5 s just to print the primes .So how am i supposed to do this in under 6s?

is there some faster io method?

The time limit is for all the test cases.

pls reply to the second post too..

printf is fast enough. Perhaps you aren't timing the actual output time, but timing how long it takes to display all numbers on your screen? This is way slower than the actual output time; try redirecting the output to a file and timing it that way.

i tried outputting to a file and noted the time.it was under      3 sec. pls ckeck what's wrong

http://discuss.codechef.com/showthread.php?t=970

thanks

pls reply

@aniruddha can u plzz suggest me a way 2 optimize the above code ? ? ? ?

Please post your query on the forum at discuss.codechef.com and post the link here. The code size is very large

The code seems to be large. . . but actually most of the part is jst initialisation of array p containing primes upto sqrt(10^9).  . .

i hv also posted this on forums as said. . . link to that is:-

http://discuss.codechef.com/showthread.php?p=2748&posted=1#post2748

@aniruddha plz check tht code. . . .the initialisation of array p containing primes upto sqrt(10^9) is in a separate text file. . . please copy and paste  that part at the place of declaration p. .  .Thank You ! !

@admin any suggestions sir ? ? ? ?:)

@aniruddha ? ? ? ?

I've already commented on the forum thread.

@anirudda : sir u hv jst asked fr d error. . . i said its TLE. . . .so plz suggest me a way to get rid of it? ? ?

in ths code i hv directly used an array cntainin primes upto 10^9 instead of generating them in my code. . .nw hw cn i further optimise it ?? ??

Thanx for ur support guys. . . CodeChef is gr8 :)

#include<stdio.h>

#include<conio.h>

void main()

{

int x,y,k;

puts("enter the limit(num   num) format    n");

scanf("%d%d",&x,&y)

for(i=x;i++;i<=y)

{   if(k==sqrt(i))

printf("%d",  i);

}

getch();

}

whats prblem in my code i hd generated all primesby searching factors frm 1 to sqrt n

#include<stdio.h>
#include<math.h>
int prime(long long n)
{
long long i,t, c1=0;
double j;
j=n ;
for(i=1;i<=(long long)sqrt(j);i++)
{
if(n%i==0)
c1++;
}
if(c1==2)
return 1;
return 0;
}
int main()
{
int i,n;
long long j,x,y;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%lld %lld",&x,&y);
for(j=x;j<=y;j++)
{
if(prime(j)==1)
printf("%lldn",j);
}
printf("n");
}
return 0;
}

is the 6 sec time limit for a single test case or all the test cases combined??

FAQ

can some one help me with this

http://www.codechef.com/viewsolution/174828

m and n are of type 'long'. %lld represents type 'long long'.

For this problem, you want to test "every factor" of a certain number to make sure its a prime. Disregarding just even number is not enough.

To test if X is prime, you only need to divide X by a number from 3 to square root of X, because anything larger than square root of X cannot be a factor of X has already been tested (i.e. When testing if 10 is a prime number, you don't need to test 10%5=0? because you already know that 10%2!=0).

To further increase your algorithm's speed, you need to use the Sieve of Eratosthenes.

To check if X is a prime number, do the following:

1. Create a huge list from 0 to 100002 (max is 100000, as given in the problem. But index 0 and 1 will not be used because prime numbers start at 1.). It's not much that much memory. You will be eliminating numbers from the list as you move along. I suggest an array. int numbers[100002];

2. Make a loop from 2 to 100002. First, set an integer (q) to 2, print out q, then cross out from your huge list of numbers any number that is a factor of two.

3. For each element in the loop, if the element has not been crossed out, then print out that number. Also, cross out any number that is a factor of that number.

4. Proceed the loop until you have finished the whole list. You should have printed out all prime numbers.

Additional info: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Are you trying to spoil the problem for everyone? Admin, are you able to delete this comment please..

@Stephen Merriman

thnks .......

finally solved it....

Can anyone explain why I am getting a wrong answer. The code is as follows:

#include<stdio.h>
using namespace std;
int main()
{
//    freopen("in","r",stdin);
//    freopen("out1","w",stdout);
int t;
long long arr[3401],count,index=1,ctr=0;
arr[0]=2;   
long long n,m,i,no;

// Generate first 3402 primes which go till square root of 10^9
for(no=3;no<31624;no+=2)
{
ctr=0;
for(i=3;i*i<=no;i+=2)
if(no%i==0)
{
ctr=1;
break;
}
if(ctr==0)
arr[index++]=no;
}
//    for(i=0;i<25;i++)
//        printf("%dn",arr[i]);
scanf("%d",&t);
count=0;
while(t--)
{
scanf("%lld %lld",&m,&n);
//if(m%2==0 )
//    m++;
//if(m==1)
//    m=2;
m=(m==1)?2:m;
no=(m%2==0)?m+1:m;
for(;no<=n;no+=2)
{
ctr=0;
for(i=0;arr[i]*arr[i]<=no;i++)
{
if(no%arr[i]==0)
{
ctr=1;
break;
}
}
if(ctr==0)
printf("%lldn",no);
}
printf("n");
}
return 0;
}

by "sieve of erasthosthenes" i can only list about 12X10^5 primes under 10^7 in 1 sec but i can not search upto 10^9.i know the problem only needs to know about nos between 1000000000 to 1000100000.but dont i need to know the status of the first 10^9 nos before finding the status of nos between 1000000000 to 1000100000.

Nope.

http://www.codechef.com/viewsolution/188742

can any body help me out getting time limit correct???

Does using a buffer to store output data and writing it alltogether at once as MichaelID & Geniusguy have done enhance the speed of the program as compared to printing out the data 1 at a time.

Will u please tell me what input u have given on which my program have given u wrong output?

It gives the wrong answer on the sample input.

can anyone please tell me, how to check out the time my program is taking to execute ... all have posted their time limits here but i don konw how to find it

How to speed up printing process in java??

(I am using System.out.println())

@abcd: i am not sure ... but i'd try the following

1. System.out.append() ... you'll need an extra n, i've seen it perform faster .

2. Use a StringBuilder to cache all the output and then append it all at once . Extremely fast , but be careful when you use it when output is too huge , will throw java.lang.OutOfMemoryError .

Your code doesn't need its output sped up. Both of your algorithms are far too slow to solve this problem regardless of what you output.

@Stephen Merriman

No,I don't think it's slow.I've used an inbuild function for it

I know what you used, and like I said, it is too slow.

Howcome this is slow??It seems to take the same amount of time as to print the numbers without even checking them for prime!,and can user-defined functions work faster than the in-build ones???

@abcd...

Well, user-defined functions can work faster than predefined ones if the predefined ones perform extra tasks/checking which you don't require. But thats NOT the issue here.

... For this particular problem , testing numbers individually isn't the best idea when you can generate the entire range in comparable time . Think/Read about algorithms for finding primes and not for primality testing. Go through the comments here if you need a hint on what technique to use.

And please, before taking any of our advice convince yourself that your current solution won't work by trying the best i/o strategy you can think of. StringBuilder 'should' work fine for the range of output you require, use it and test the time with or without primality testing.

and yeah , i missed it in the last list of fast i/o suggestions. Did you try BufferedOutputStream ?. It should be way faster than println , but not as fast as using the StringBuilder . For a string s, you'd write with buffStrmObject.write(s.getBytes());. and don't forget to flush/close the stream before you end .

You are probably also confusing output time with display time. Displaying a large amount of numbers in a command prompt is very slow, but that's not part of your execution time. If you redirect the output to a file instead of printing it to a screen you'll find that it isn't slow at all.

where am i wrong in my code can anyone can tell me????

I used individual bits to represent numbers and followed the sieve of eratosthenes. I can generate all primes upto 10^7 in less than a second. The iterating through and printing the numbers(on a file) for larger values takes very long(upto 2 seconds in larger cases). For 10 very large test cases, this still leaves me at approx 18-21 seconds. This problem is intriguing in the sense that it was solved by some in 0.03 seconds. Should i use c instead of c++ to speed this up? OR am i supposed to print all the prime numbers? Is this a problem on I/O rather than on finding primes / primality testing?

Well, you should never use cin and cout as mentioned in the FAQ which you of course read before posting a comment ;) But your algorithm is simply too slow. You have ignored the fact that n-m <= 100000; solutions to this problem aren't expected to generate all primes from 1 up to 10^9.

You should be able to do it in roughly 0.05s without any tricks and in half that time with buffered output piped to a file. Just make your algorithm do exactly what is required, and nothing more.

@Admin:

My solution works fairly fast on my pc. My solution is: http://www.codechef.com/viewsolution/271683

What more could be optimised?

@Admin:

Once again, my solution is here: http://www.codechef.com/viewsolution/271732

All the cases work really fast when I try.

@ Admin: Can you plz tell me why am I getting a runtime error when I submit? The code is working fine locally and I am getting no such errors.

@Admin:

Please tell me where am I exceeding time limit? I've tried many ways...

http://www.codechef.com/viewsolution/272144

http://www.codechef.com/viewsolution/271732

http://www.codechef.com/viewsolution/271683

@Opeth : It could be something else ... but in your primesMN , wouldn't all the numbers between m and n be checked if divisible by prime[index] when prime[index] is n itself ? In my opinion this process would also be very time consuming for large prime numbers between m and n.

If all you want is the first number between m and n divisible by prime[index], it can be done in a single step. I can give you a hint if you want one.

@Disha ... have you tested your program against the sample input case ?? I believe, you're not reading input correctly.

@Antarpreet Singh:

Hey this is an imprved version of primesMN, but I'm still over time limit:

void primesMN(int m, int n, bool primeMN[])
{
int index = 0, i, mul, nonPrime, start;
index = 0; start = 0;
while(1)
{
for(i=start; i<=n-m; i++)
{
if((i+m)%primes[index]==0)
{
mul = i;
break;
}
}
if(primes[index]==(mul+m))
nonPrime = primes[index] + mul;
else nonPrime = mul;

for(i=nonPrime; i<=n-m; i+=primes[index])
{
primeMN[i] = notprime;
}
for(i=0;i<=n-m;i++)
{
if(primeMN[i]==prime) {start = i; break;}
}
index++;
if(primes[index]==31991||primes[index]>=n) break;
}
i=0;
if(m==1) i=1;
for(;i<=n-m;i++)
{
if(primeMN[i]==prime)
printf("%dn", i+m);
}

}

@Antarpreet Singh:

Hey this is an imprved version of primesMN, but I'm still over time limit:

void primesMN(int m, int n, bool primeMN[])
{
int index = 0, i, mul, nonPrime, start;
index = 0; start = 0;
while(1)
{
for(i=start; i<=n-m; i++)
    {
    if((i+m)%primes[index]==0)
        {
        mul = i;
        break;
        }
    }
if(primes[index]==(mul+m))
    nonPrime = primes[index] + mul;
else nonPrime = mul;

for(i=nonPrime; i<=n-m; i+=primes[index])
    {
    primeMN[i] = notprime;
    }
for(i=0;i<=n-m;i++)
    {
    if(primeMN[i]==prime) {start = i; break;}
    }
index++;
if(primes[index]==31991||primes[index]>=n) break;
}
i=0;
if(m==1) i=1;
for(;i<=n-m;i++)
    {
    if(primeMN[i]==prime)
    printf("%dn", i+m);
    }

}

Sorry for posting that twice, some problem with my connection. Won't happen again.

Please do NOT post code here ... just post a link if you have to. Your program still has the same problem i pointed out before, you can achieve the same effect of that loop using a simple mathematical formula involving integer arithmetic. I tested your solution http://www.codechef.com/viewsolution/272314 after replacing lines 124-128 with my own code. It got accepted in .06 seconds.

@Antarpreet Singh:

Thanks finally got accepted in 0.07 second, although I want to improve my time. Can CodeChef not allow us to view other people's solutions? That would help us in approaching a problem in many different ways...

http://www.codechef.com/viewsolution/272529

somebody help!!! i don't know why m getting a WA for this!!

somebody help .. please.. i hve cross checked the results for many ranges, still an WA.. please help!!!

#include<stdio.h>

#include<math.h>

#include<algorithm>

#include<iostream>

using namespace std;

bool b[100020];

int c[100002];

int d[100002];

int e[100002];

int main()

{

int i,j;

for(i=0;i<=100000;i++)

{d[i]=1;

e[i]=1;

}

for( i=0;i<=(int)sqrt(1000000000);i++)

b[i]=1;

b[0]=0;

b[1]=0;

b[2]=1;

int test;

for( j=2;j<=(int)(sqrt(sqrt(1000000000)));j++)

{

if(b[j])

{

for(int k=j*j;k<=(int)(sqrt(1000000000));k+=j)

b[k]=0;

}

}

int ind=0;

for(int l=0;l<=(int)(sqrt(1000000000));l++)

{

if(b[l])

{c[ind++]=l;}

}

scanf("%d",&test);

for(int t=0;t<test;t++)

{

int n1,n2;

scanf("%d %d",&n1,&n2);

if(n2<=(int)(sqrt(1000000000)))

{

int flag2=0;

for( j=n1;j<=n2;j++)

{

if(b[j])

{

flag2=1;

printf("%dn",j);

}

}

//if(!flag2)

//printf("n");

printf("n");

continue;

}

int d_ind=0;

int tempe;

if(n1==1)

n1++;

if(n1!=2)

{

if(n1%2==0)

n1++;

tempe=2;

}

else

tempe=1;

for(i=0;i<=n2-n1;i+=tempe)

{//d[i]=1;

e[i]=1;

}

//memset(e,1,100000);

for(j=n1 ;j<=n2;j+=tempe)

{

int flag=1;

if(e[j-n1])

{

flag=0;

for(int p=0;p<ind;p++)

{

if(j%c[p]==0&&j!=c[p])

{

flag=1;

for(int g=j-n1;g<=n2-n1;g+=c[p])

e[g]=0;

//b[j]=0;

break;

}

}

if(flag==0)

{

//c[ind++]=j;

//    d[d_ind++]=j;

//

printf("%dn",j);

}

}

}

int flag3=0;

//  for( j=0;j<d_ind;j++)

//{

//      flag3=1;

//}

//if(!flag3)

printf("n");

//printf("done %d %dn",n1,n2);

//    return 0;

}

}

finally got it in 0.06.. all credits to stephen merriman.. u rock dude m/

i have read Sieve_of_Eratosthenes but finding it difficult to implement for to calculate all prime no. between two numbers....help me

plz help...

here is my code...

#include <stdio.h>

#include <stdlib.h>

#include <stdbool.h>

#include <math.h>

long int n[11]={0},m[11]={0};

void print_prime(long int r1,long int lim)

{

long int i, j;

lim += 1;

bool *primes = calloc(lim, sizeof(bool));

long int sqrtlim = sqrt(lim);

for (i = 2; i <= sqrtlim; i++)

if (!primes[i])

for (j = i * i; j < lim; j += i)

primes[j] = true;

for (i = r1; i < lim; i++)

if (!primes[i]&& i!=1)

printf("n%d", i);

printf("n");

}

int main()

{    int t,i;

scanf("%d",&t);

for(i=0;i<t;i++)

{

scanf("%ld %ld",&m[i],&n[i]);

}

for(i=0;i<t;i++)

print_prime(m[i],n[i]);

return 0;

}

i m able to run it successfully on dev c++

it shows me some runtime error here..is it due to arrays or what

plz gimme some hint

@sanchit - maybe calloc is failing. plus where are you deallocating the memory. cant see free in your code??

if you are freeing the memory, then calling calloc 10 times  for 1 lakh integers will most definitely fail.

Also, since speed is very important here, so better to use static allocation than dynamic allocation as memory allocation is very time intensive.

good luck!

Can some mod look at my code and comment why it is giving wrong answer?

I have used my code to generate first 10000 integers and matched them with list on net.

also i have checked my code to be "boundary-safe"

i am feeling clueless now.

i am new to code chef this is my solution it worked fine on on my pc but it's showing runtime exception please some one help me with it..

# include<stdio.h>
void checkprime(int k)
{
int i,rem;
for(i=2;i<=(k/2);i++)
{
rem=k%i;
//printf("for number %d when divided by %d remainder is %dn",k,i,rem);
if(rem==0)
return;
}
printf("%dn",k);
}

int main()
{
int a,b,i;
printf("enter the values of a and b");
scanf("%d%d",&a,&b);
if(a<6&&b>=6)
{
if(a==2||a==1)
printf("2n3n");
if(a==3)
printf("3n");
}
if(a<6&&b<=6)
{
if(a==2)
{
if(b==5)
printf("2n3n5n");
if(b==4||b==3)
printf("2n3n");
}
if(a==3)
{
if(b==5)
printf("3n5n");
if(b==4||b==3)
printf("3n");
}
if(a>4)
{
printf("5");
}
}

for((i=(a-1)/6+1);(6*i+1)<=b;i++)
{
checkprime(6*i-1);
checkprime(6*i+1);
}

}

the n's in the codes are slashn's in the comments it is showing that way

The definition of runtime error in C is when your main method does anything but return 0. Youaren't returning 0, therefore you get a runtime error.

You should read the FAQ.

stephen thanks for helping me. now the runtime error is gone but it shows it's wrong.i tried for various input it worked fine.

i used the concept that every prime number except 2,3 every prime  number  can be expressed in the form of 6n+1 or 6n-1.if u could figure it out where i am gone wrong can u please help me with it.

I already did. I said you should read the FAQ for precisely that reason.

Hello.  My code is working perfectly fine.  I checked with the extreme inputs and verified them with the list of primes i downloaded from the internet.  But I am getting wrong answer.

Can anyone please help me?

http://www.codechef.com/viewsolution/290274

finally somehow managed to successfully submit my solution.

a tip for all those struggling to find errors in their code:

write a test program that calls your prime no. generating function with inputs from (1,100), (2,100), (3,100), .... (100,100)

and for every output, check if any false prime no. is generated or the no. of prime nos. generated are less than expected prime nos. something like code below. you need to replace MyOutput appropriately.

int primes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
int isPrime(int k)
{
for(int i=0; i<sizeof(primes)/sizeof(int); ++i)
{
if(primes[i]==k)
return 1;
}
return 0;
}

//total primes between start and end; using known set.
int totalprimes(int start, int end)
{
int k=0;
int j=0;
while(primes[j]<start && j<sizeof(primes)/sizeof(int))
++j;
while(primes[j]<end && j<sizeof(primes)/sizeof(int))
{
k++;
j++;
}
return k;
}

void RunTestCase()
{
int start=1, end=100;
int iter = start;
bool bSuccess = true;
while(iter <= end)
{
MyOutput output = Generate(iter,end);

for each number k in output

if(!isPrime(k))
{
cout<<"nFalse prime no. detected: "<<k;
bSuccess = false;
break;
}
nprimes++;
k=-1;
}
if(nprimes != totalprimes(iter,end))
{
bSuccess = false;
cout<<"nTotal primes nos less than expected";
}

if(!bSuccess)
{
cout<<"nFailed for range: "<<iter<<"-"<<end;
break;
}
++iter;
}
if(bSuccess)
{
cout<<"nTest case passed successfully";
}
}

Hope it helps someone. If I had written this fxn earlier, it wud have saved me lot of time.

a '{' after "for each number k in output" is missing.

i m new to programing. kindly tell if my program will work or not n wat is the problem with it

plz help me.....

#include<stdio.h>
void main(int ar, char *ac[])
{
int x=0,y=0,i=0,j=0,k=0;
printf("enter the first number : ");
scanf("%d",&x);
printf("enter the second number : ");
scanf("%d",&y);
for(i=x;i<=y;i++)
{
k=0;
for(j=2;j<i;j++)
{
if(i%j==0)
{
k=k+1;
}
}
if(k==0)
{
printf("tn%d",i);
}
}
}

1) Your program isn't doing the the problem statement tells you to do - for example, the first number is the number of test cases, but you don't have that in your program.

2) The first line of the sample output is 2. The first line of your output is 'enter the first number: enter the second number:'. These aren't the same, so you won't get judged as correct.

3) Have you tested your code on an input with m and n very large? Does it run in under 6 seconds?

You should read the FAQ first, as it covers other issues with your program too.

thanx 4 ur support. :-)

but wat i thought was it was asked to generate prime numbers b/w any two given numbers. an that is wat i did. n ya it works for bigger numbers olso but thanx.

That is what it is supposed to do; but it didn't say to output text at the start like "Enter a number". Your answer is matched character by character to the real answer.

I'm afraid you can't have checked many large inputs - your code doesn't have a hope of running in time in the worst case (10 cases of the largest possible size).

hey please check the test cases... i kept on getting WA for a specific length of an array.. when i increased the length of the array by 1 i got AC

Nothing is wrong with the test cases; it was a bug in your code.

hi, any body help me why time limit exit?

my code are given below

#include<stdio.h>

int isprime(long long n);
int main()
{
long long  a,b;

int ks,i;

scanf("%d",&ks);
for(i=0;i<ks;i++)
{
scanf("%lld %lld",&a,&b);
for(;a<=b;a++)
{
if(isprime(a))
{
printf("%lldn",a);
}
}
printf("n");


}
return 0;
}
int isprime(long long n)
{
long long i;
if(n==0||n==1)
return 0;
if(n==2)
return 1;
if(n%2==0)
return 0;
for(i=3;i*i<=n;i+=2)
if(n%i==0)
return 0;
return 1;

}

@stephen... i submitted code with a max prime of 31607... when i calculated one more prime after that 31627 then i got AC and 31627*31627 is greater than the range.. so.. i m not really sure how i m wrong.. plzz explain... sorry for writing those values.. but i cud nt have been able to explain if i wud nt have written those

I know, I saw your code - with 31607.  When you test your program on the largest input, when does your loop to test factors end? Every prime has prime*prime less than the number, so your loop keeps going until it tries an array value outside of the valid range, after which anything could happen.

can not understand why a I get wrong answer

http://www.codechef.com/viewsolution/302949

I m getting 'wrong answer' for my program,though when i test it i dont see anything wrong.

@Admin:Can u give some test cases,so i can better evaluate my program.

i m getting tle plzzzzzzzzzz help

its showing runtime error. sum1 plz help!!! ihave tried 100 times

http://www.codechef.com/viewsolution/314764

@Admin, my code is taking only 2.5M memory even then i am getting runtime error(SIGSGEV). i removed an array of 3000 int elements from main() and declared it global, it is still giving runtime error(OTHER). code is running perfect on my system and theres no array bound problem too/no division by zero or other ambiguity. i am unable to decipher the problem.. :(

@Admin, my code is taking only 2.5M memory even then i am getting runtime error(SIGSGEV). i removed an array of 3000 int elements from main() and declared it global, it is still giving runtime error(OTHER). code is running perfect on my system and theres no array bound problem too/no division by zero or other ambiguity. i am unable to decipher the problem.. :(

@abhay same problem with me

@admin plz answer our to our problem

@Admin, can you please check what is wrong with my code. it gives Runtime error(OTHER).. heres url for that http://www.codechef.com/viewsolution/315229

@admin, i am fedup of watching runtime error again and again :( atleast error should change :p plz check where my code lacks.

Well, the statement says n-m<=100000, and you seem to have forgotten about one of those 0s.

@stephen, Thanks man! :) i think it should be submitted now. you have great observation skills :)

@stephen plz help me i have considered all the cases still getting runtime  error. plz check my code n tell me wats the problem..

http://www.codechef.com/viewsolution/315094

wohoo!!! my best solution ever.. did in 0.05 seconds :D m loving it

I have found a nice thing.

All prime number are at even distance from 3 except 2.

increment your parent loop with +=2 rather than ++, this will ewduce your loop.

all prime numbers are at even distance from one another so start incrementing with +=2 wherever you find yur first prime number

I did the program in C language....it worked perfectly in the compiler on my PC...i used the Turbo C compiler...But here it is showing compiler error...m unable to understand anything...plz help!!!!

@ankit anand. it is a another way of saying "2 is the only even prime number". if 3+odd="even" which can never be prime. and yes, +2 reduces the task of loop by half rather than +1.

My code gives the exact output. But time limit is the problem.Not sure if creating objects is the problem. please help me in optimizing the code.

#include <iostream>

using namespace std;

class prime{

long a,b;

public:

void getdata(void);

void primedata(void);

};

void prime::getdata(void){

cin >>a>>b;

}

void prime::primedata(void){

long count=0;

for(long i=1;i<=b;i++){

if(i>=a){

for(long j=1;j<=i;j++){

if((i%j)==0){

count ++;

}

}

if(count ==2){

cout <<i<<endl;

}

count =0;

}

}

}

int main(){

long number=0;

cout<<"INPUT"<<endl;

cin >>number;

prime item[number];

for(long i=1;i<=number;i++){

item[i].getdata();

}

cout<<"OUTPUT"<<endl;

for(long i=1;i<=number;i++){

item[i].primedata();

cout<<"n";

}

return 0;

}

Firstly, your code doesn't even give the right output on the sample input; the sample output doesn't have the words INPUT or OUTPUT anywhere in it.

Secondly, have you tried an input file with 10 cases of the largest possible size? That will show why your code is timing out.

You should read the FAQ as well, since your code has some other issues.

Hi,

I read the FAQ section and tried to submit the "TEST" program to start with.(http://www.codechef.com/problems/TEST)

Question is - Does Code chef use an input and output file for testing this program as mentioned in the FAQ section?
I am not able to understand this, When does codechef use the input of type "test.exe < in.txt > out.txt"  to test the program and when does statements such as "std::cin.get(c)" [incase of C++ programming] is used.
Please explain asap, as i am not able to proceed in submitting any other solutions.

Thanks in advance.

http://www.codechef.com/viewsolution/355139

can some body help me out..?

it's working well on my system but here it says (Runtime Error/ OTHERS)

please.. can somebody tell me whats wrong with the code

http://www.codechef.com/viewsolution/355150

i removed da println statements... even then it's not working

Read the FAQ.

What wrong with this site my every submissions are showing 0 memory and 0 time

yea... checked the FAQ...can some1 tell wherein it uses a loads of memory

I dont know wht is the problem in my code... its showing runtime error.... i didnt use much memory...

Your code throws an exception when run on the sample input. You should probably test your code with that before asking for help.

I'll try to help all the people,who has some troubles with this problem.You should save all the prime numbers from 2 to sqrt(maxM).then check all the numbers between n and m,by trying to divide it by every prime number,that we've saved at the beginning.By the way,your cycle should look like it: 
While i>=prime[i]*prime[i] do

begin

............

end;

but not like this.

While round(sqrt(i))>=prime[i] do

.....

....

....

First varian got AC in 2.5 seconds,but the second one got TL,so it works ore than 6 seconds!O_O

Good luck:)

i need help. my program is successfully compiling in Dev-C++ 4.9.9.2 but the judge is showing a runtime error. i have not included conio.h and any of its functions.

Please don't post code here; read the FAQ. The amount of memory you are trying to declare is far too much.

i have also tried reducing array size to 100. even then it shows a runtime error. so my array size is anot an issue.

Of course you can't just reduce it to 100, because your algorithm requires you to store that much memory. But that much memory is not allowed on Codechef as I said; so you must think of an algorithm which uses a lot less memory.

I changed my algorithm and it uses very less memory now(only 4000 ints which is 2.6 MB) but I'm still getting TLE.

here's my code:

http://www.codechef.com/viewsolution/385202

further optimized code: http://www.codechef.com/viewsolution/385251 still TLE

code: http://www.codechef.com/viewsolution/385282

Now it's showing SIGSEGV

code: http://www.codechef.com/viewsolution/385301

SIGFPE

finally :D working code: http://www.codechef.com/viewsolution/385304

#include<iostream>

#include<unistd.h>

using namespace std;

int main()

{

int first,last,curr=1,i=0,j,arr[25000];

cout<<"Enter the limiting non";

cin>>first>>second;

cout<<"Prime no's aren";

alarm(6);//for checking six second

while(curr<=second)

{

if(i==0)

{

arr[i++]=2;

if(first<=2)

cout<<"2";

}

else

{

for(j=0;j<i;j++)

{

if(curr%arr[j]==0)

break;

}

if(j==i)

{

arr[i++]=curr;

if(curr>=first)

cout<<curr<<endl;

}

}

curr++;

}

}

i typed that code.

its working properly.

bt when i submitted they told wrong answer whats wrong with it can any 1 tell.

my pgm is able to produce prime no within range 1 to 2,40,000 within 6 second.

bt judges r telling that my code is wrong bt its working fine.

can any one help me in it...

The problem says pretty clearly you will need to generate primes a lot bigger than that.. have you tested your code on the largest possible input?

Also, you should read the FAQ. You are outputting a lot more than you are meant to.

All right guys, I assume all of you know how to solve this problem, but are getting TLE.

First, the only way to know if a number is prime is to divide it by all the primes before the square root of that number.

It's not fast enough to just rule out all the even numbers.

There's this magic function, f(x) = 6x +- 1, it contains ALL the primes EXCEPT 2 and 3 (and other numbers that are not primes, but I assure you all the primes are members of that function). Rule out all the numbers that are not members of that function, and test only for those.

Finally, use dynamic programming, save all the primes that you have found for future reference.

@Admin Please make sure that the time limit is correct(6 sec for all test cases),as my program runs in 4.74255 sec for 10 worst test cases(n-m=10^5 and n=10^9),and it still shows TLE!!!!.please check that!!

The time limit is correct. Your computer is probably faster than the judge, which is normally the case.

i tried my best to optimise the code but still getting the same "TIME LIMIT EXCEEDED"

i dont understand why please anybody help me

one of my solution link is below:

http://www.codechef.com/viewsolution/404621

@sidhartha

instead of checking from 3 to sqrt(num) to see whether num is aprime numnber or not

you should check for divisibility by only prime numbers less than equalto sqrt(num) to check whether num is prime or not

plzz can any 1 give me a test case where my code fails plzzzzzzzzzzzzzzzzz :-( I have tried a lot :-( still I am gettin a wrong answer :-( :-( http://www.codechef.com/viewsolution/409405

I have used the sieve of eratosthenes algorithm but still I am getting TLE error

Here is my code

http://www.codechef.com/viewsolution/426763

You can make a lot of optimisations to your current sieve (you're doing too many multiplications), but most importantly you'll need to use the fact that n and m are quite close to speed up your algorithm.

Can anyone tell me what is wrong with my logic?

I create an array of all primes which are lesser than or equal to sqrt(1,000,000,000) and then test for each number in the range whether it is divisible by any of the primes. If it is divisible, then not a prime. If it is not divisible by any of the primes in the array, then it is a prime.

I think the implementation of the above logic is correct in the code. Please let me know if there are any errors in the logic or in the implementation.

The link to my code:http://www.codechef.com/viewsolution/433919

First I got a lot of TLE's then I improved my code a lot but now I'm getting WA.Please tell me if there is any problem with the output format. I think my algo is fast enough.

Here is my code:

http://www.codechef.com/viewsolution/482308

i am confused about this statement

" Separate the answers for each test case by an empty line. "

every newline after testcase or newline between testcase ?

following is my code....... its giving TLE... what else should i optimize

#include<iostream>

#include<math.h>

using namespace std;

long long prim_a[1000000];

long long prim_b[1000000];

void prime_genr()

{

long long q=2;

long long sqr=sqrt(100000);

for(long long i=q;i<sqr;i++)

{

if(prim_a[i]==0)

{

for(long long j=i+1;j<sqr;j++)

{

if(j%i==0)

{

prim_a[j]=-1;

}

}

}

}

long long l=0;

for(long long i=2;i<100000;i++)

{

if(prim_a[i]==0)

{

prim_b[l++]=i;

}

}

}

main()

{long long t,n1,n2,flag;

prime_genr();

cin>>t;

while(t)

{

--t;

cin>>n1>>n2;

for(long long i=n1;i<=n2;i++)

{flag=0;

for(long long j=0;prim_b[j]<=sqrt(i);j++)

{

if(i%prim_b[j]==0)

{

flag=1;

break;

}

}

if(flag!=1&&i!=1)

cout<<i<<"n";

}

cout<<"n";

}

}

HOW CAN I REDUCE TIME FOR THIS SIMPLE CODE;

#include<iostream>

#include<math.h>

using namespace std;

void prime(int);

void p(int);

int main()

{

int m,n,t;

cin>>t;

while(t>0)

{

cin>>m>>n;

for(int i=m;i<=n;i++)

prime(i);

t--;

}

}

void prime(int n)

{

int flag=0;

if(n==1)

return;

for(int i=2;i<=sqrt(n);i++)

{

if(n%i==0)

{

flag=1;

break;

}

}

if(flag==0)

cout<<n<<endl;

}

Someone please tell me, why I am getting a runtime error foe this code :

http://www.codechef.com/viewsolution/523516

#include<stdio.h>
#include<math.h>
main()
{
int m,n,i,c,j;

printf("Enter the values of m and n (m < n): ");
scanf("%d %d", &m, &n);

for(i=m; i<=n; i++)
{
c=0;
for(j=2;j<=sqrt(i);j++)
{
if(i%j==0)
c++;
}

if(c==0)  
printf("%3d n", i);
}

getch();
}


What is the problem with this code????????

@admin: I'm getting this on my laptop:

time ./prime_gen.exe < in > out

real    0m1.217s
user    0m0.015s
sys     0m0.015s

The test file I'm using is:

$ cat in
10
999900000 1000000000
999900000 1000000000
999900000 1000000000
999900000 1000000000
999900000 1000000000
999900000 1000000000
999900000 1000000000
999900000 1000000000
999900000 1000000000
1 50

when I submit the code I get a Time Exceeded error. I'm I calculating wrongly the time on my machine?

sergico

@Admin: I applied my check of primes only on numbers of form 6k+/- 1, so I actually performed my check on 1/3 rd of the numbers. But still my code is exceeding the time limit. Plss help me out with some suggestions. I am attaching my code for any further suggestions.

Thank you.

#include <cstdio>
#include <iostream>
#include <cmath>

using namespace std;


void primeCheck(int num)
{
int flag, lim, k;
flag = 0;
if ((num % 2) == 0)
{
flag = 1;
return;
}

if ((num % 3) == 0)
{
flag = 1;
return;
}

lim = sqrt((double)num);

for ( k = 6; k < lim - 1; k+=6 )
{
if ((num % (k-1)) == 0)
{
flag = 1;
return;
}
else if ((num % (k+1)) == 0)
{   
flag = 1;
return;
}
}
if (k-1 < lim)
{
if ((num % (k-1)) == 0)
{
flag = 1;
}
}

if (flag == 0)
{
cout<< num<<endl;
}
}

int
main()
{
int numOfInputs, possNextPrm, num, k, flag, lim, inputs[20], i;

cin>> numOfInputs;

for (i = 0; i< numOfInputs; i++)
{
cin>> inputs[2*i];
cin>> inputs[2*i + 1];
}

for (i = 0; i< numOfInputs; i++)
{
cout<< endl;
if (inputs[2*i] < 3)
printf("2n");
if (inputs[2*i] < 4)
printf("3n");

if (inputs[2*i] % 6 == 0)
primeCheck(inputs[2*i] + 1);

possNextPrm = 6*(inputs[2*i]/6 + 1);

for ( num = possNextPrm; num <= inputs[2*i + 1]; num = num + 6)
{
primeCheck(num - 1);

if (num+1 <= inputs[2*i + 1])
primeCheck(num + 1);
}
}   
return 0;
}