Prime Generator

All submissions for this problem are available.
Shridhar wants to generate some prime numbers for his cryptosystem. Help him!
Your task is to generate all prime numbers between two given numbers.
Input
The first line contains t, the number of test cases (less then or equal to 10).
Followed by t lines which contain two numbers m and n (1 <= m <= n <= 1000000000, nm<=100000) separated by a space.
Output
For every test case print all prime numbers p such that m <= p <= n,
one number per line. Separate the answers for each test case by an empty line.
Example
Input: 2 1 10 3 5 Output: 2 3 5 7 3 5
Warning: large Input/Output data, be careful with certain languages (though most should be OK if the algorithm is well designed)
Author:  admin 
Tags  admin 
Date Added:  1122008 
Time Limit:  6 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 
Brute force doesn't seem to work? Anybody with any pointers?
My opinion is basically try
hey hii this karan. i have
Just discarding even numbers
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
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
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
@Neerav you need a faster algorithm :)
try removing all nos with 5
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
:) The range of the numbers
i am first saving all the
Yes, there are a lot of prime
my program in java fails
my program in java fails compilation...
its running fine on my machine.
Can anyone tell why?
Read the FAQ / Help pages.
Read the FAQ / Help pages.
Hey I used Sieve of
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
There are a lot of primes less than 10^9
Hey I have used what they
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
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
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
We will definitely doing this.
For a single test case my
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
So you'll need to make your algorithm a lot faster then :)
hi aewl..i am new hea..can
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
The largest n can be is less than 2^30, so it will fit inside a normal int perfectly fine.
#include <iostream>#include
#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[i1] == 1){
for(long j = i+i; j <= p; j += i){
list[j1] = 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[j1] == 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
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
Stephen,plzzzzz tell me how to resolve this problem.......
plzzzzzzz buddy help me.....
thankx in advance.....
@mukul: Simple eratosthenes'
@mukul:
Simple eratosthenes' sieve would probably not work here.
@mukul you need to generate
@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
I am using seive of eratosthenes but still my program is taking 30sec to go for extreme case ie 9999900001000000000 can anyone help me
I've got TLEs. But I
I've got TLEs. But I didn't think my approach was totally wrong. So I focused on what makes program slow, and found it.
Do not use ANY CONTAINER for storing prime numbers BUT native array.
Forget it if you have a plan to use very faster algorithm like MillerRabin's, or AKS.
mine is taking 11 secs :(
mine is taking 11 secs :(
mine takes less than a second
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
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
The time limit is for all the test cases.
pls reply to the second post
pls reply to the second post too..
printf is fast enough.
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
i tried outputting to a file and noted the time.it was under 3 sec. pls ckeck what's wrong
http://discussed.codechef.com/showthread.php?t=970
thanks
pls reply
pls reply
The code seems to be 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://discussed.codechef.com/showthread.php?p=2748&posted=1#post2748
@aniruddha plz check tht
@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 ?
@admin any suggestions sir ? ? ? ?:)
@aniruddha ? ? ? ?
@aniruddha ? ? ? ?
I've already commented on the
I've already commented on the forum thread.
@anirudda : sir u hv jst
@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. .
Thanx for ur support guys. . . CodeChef is gr8 :)
whats prblem in my code i hd
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
is the 6 sec time limit for a single test case or all the test cases combined??
FAQ
FAQ
can some one help me with
can some one help me with this
http://www.codechef.com/viewsolution/174828
m and n are of type 'long'.
m and n are of type 'long'. %lld represents type 'long long'.
For this problem, you want to
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
Are you trying to spoil the problem for everyone? Admin, are you able to delete this comment please..
@Stephen Merriman thnks
@Stephen Merriman
thnks .......
finally solved it....
Can anyone explain why I am
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"
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.
Nope.
http://www.codechef.com/views
http://www.codechef.com/viewsolution/188742
can any body help me out getting time limit correct???
Does using a buffer to store
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
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
It gives the wrong answer on the sample input.
can anyone please tell me,
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
How to speed up printing process in java??
(I am using System.out.println())
@abcd: i am not sure ... but
@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
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
@Stephen Merriman
No,I don't think it's slow.I've used an inbuild function for it
I know what you used, and
I know what you used, and like I said, it is too slow.
Howcome this is slow??It
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 userdefined functions work faster than the inbuild ones???
@abcd... Well, userdefined
@abcd...
Well, userdefined 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
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
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
where am i wrong in my code can anyone can tell me????
I used individual bits to
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 1821 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
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 nm <= 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
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
@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
@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
@ 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
@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
@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
@Disha ... have you tested your program against the sample input case ?? I believe, you're not reading input correctly.
@Antarpreet Singh:Hey this is
@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<=nm; 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<=nm; i+=primes[index])
{
primeMN[i] = notprime;
}
for(i=0;i<=nm;i++)
{
if(primeMN[i]==prime) {start = i; break;}
}
index++;
if(primes[index]==31991primes[index]>=n) break;
}
i=0;
if(m==1) i=1;
for(;i<=nm;i++)
{
if(primeMN[i]==prime)
printf("%dn", i+m);
}
}
Sorry for posting that twice,
Sorry for posting that twice, some problem with my connection. Won't happen again.
Please do NOT post code here
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 124128 with my own code. It got accepted in .06 seconds.
@Antarpreet Singh: Thanks
@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/views
http://www.codechef.com/viewsolution/272529
somebody help!!! i don't know why m getting a WA for this!!
somebody help .. please.. i
somebody help .. please.. i hve cross checked the results for many ranges, still an WA.. please help!!!
#include<stdio.h> #include<m
#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<=n2n1;i+=tempe)
{//d[i]=1;
e[i]=1;
}
//memset(e,1,100000);
for(j=n1 ;j<=n2;j+=tempe)
{
int flag=1;
if(e[jn1])
{
flag=0;
for(int p=0;p<ind;p++)
{
if(j%c[p]==0&&j!=c[p])
{
flag=1;
for(int g=jn1;g<=n2n1;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
finally got it in 0.06.. all credits to stephen merriman.. u rock dude m/
i have
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
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
@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
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 "boundarysafe"
i am feeling clueless now.
i am new to code chef this is
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==2a==1)
printf("2n3n");
if(a==3)
printf("3n");
}
if(a<6&&b<=6)
{
if(a==2)
{
if(b==5)
printf("2n3n5n");
if(b==4b==3)
printf("2n3n");
}
if(a==3)
{
if(b==5)
printf("3n5n");
if(b==4b==3)
printf("3n");
}
if(a>4)
{
printf("5");
}
}
for((i=(a1)/6+1);(6*i+1)<=b;i++)
{
checkprime(6*i1);
checkprime(6*i+1);
}
}
the n's in the codes are
the n's in the codes are slashn's in the comments it is showing that way
The definition of runtime
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
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 6n1.if u could figure it out where i am gone wrong can u please help me with it.
I already did. I said you
I already did. I said you should read the FAQ for precisely that reason.
Hello. My code is working
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
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
a '{' after "for each number k in output" is missing.
i m new to programing. kindly
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
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
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
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
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
Nothing is wrong with the test cases; it was a bug in your code.
hi, any body help me why time
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==0n==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
@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 
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
can not understand why a I get wrong answer
http://www.codechef.com/viewsolution/302949
I m getting 'wrong answer'
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
i m getting tle plzzzzzzzzzz help
its showing runtime error.
its showing runtime error. sum1 plz help!!! ihave tried 100 times
http://www.codechef.com/viewsolution/314764
@Admin, my code is taking
@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
@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
@abhay same problem with me
@admin plz answer our to our
@admin plz answer our to our problem
@Admin, can you please check
@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
@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
Well, the statement says nm<=100000, and you seem to have forgotten about one of those 0s.
@stephen, Thanks man! :) i
@stephen, Thanks man! :) i think it should be submitted now. you have great observation skills :)
@stephen plz help me i have
@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
wohoo!!! my best solution ever.. did in 0.05 seconds :D m loving it
I have found a nice
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
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
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
@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
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
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
Hi,
I read the FAQ section and tried to submit the "TEST" program to start with.(http://www.codechef.com/problems/TEST)
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.
Thanks in advance.
Question is  Does Code chef
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.
my program run without any
http://www.codechef.com/views
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/views
http://www.codechef.com/viewsolution/355150
i removed da println statements... even then it's not working
Read the FAQ.
Read the FAQ.
What wrong with this site my
What wrong with this site my every submissions are showing 0 memory and 0 time
yea... checked the FAQ...can
yea... checked the FAQ...can some1 tell wherein it uses a loads of memory
I dont know wht is the
I dont know wht is the problem in my code... its showing runtime error.... i didnt use much memory...
Your code throws an exception
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
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
i need help. my program is successfully compiling in DevC++ 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;
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
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
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
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:
further optimized code: http://www.codechef.com/viewsolution/385251 still TLE
code:
code: http://www.codechef.com/viewsolution/385282
Now it's showing SIGSEGV
code:
code: http://www.codechef.com/viewsolution/385301
SIGFPE
finally :D working code:
finally :D working code: http://www.codechef.com/viewsolution/385304
#include<iostream> #include<u
#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
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
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
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
@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(nm=10^5 and n=10^9),and it still shows TLE!!!!.please check that!!
The time limit is correct.
The time limit is correct. Your computer is probably faster than the judge, which is normally the case.
i tried my best to optimise
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
@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
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
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
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
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
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
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.......
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
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
Someone please tell me, why I am getting a runtime error foe this code :
http://www.codechef.com/viewsolution/523516
#include<stdio.h>#include<mat
#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
@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
@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 % (k1)) == 0)
{
flag = 1;
return;
}
else if ((num % (k+1)) == 0)
{
flag = 1;
return;
}
}
if (k1 < lim)
{
if ((num % (k1)) == 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;
}
@Admin :  Is the problem
I Finally got it!!!:)
why I am getting wrong answer
plz kindly help me ,i m
Could anyone tell me why is
Please tell me why I am
@Stephen : My JAVA code is
8 1 100001 100000
@admin: i always get time
hiii my code ran succesfully
@coder1 & rahulkumar7887: TLE
Please someone help me to
@admin: I am getting run
Use the sieves
I just don't get it. I
I submitted the code but when
hey!!! i m getting short in
plzz....do help!!! the code i
http://www.codechef.com/views
>.> I'm new here. What is the
Can somebody explain why the
@abhinavchdhry you are only
@lelouch you have to read
can anyone tell me ,why i am
Well, I am tired and
Hello Admin! I am getting
hello admin, what's mean by
Why am i getting runtime
My code works well wen i run
i am getting a nzec error in
i can't submit this problem
please tell how do i optimize
why am i not able to submit
@ admin : hello sir, i am
@admin why cant i submit in c
why cant i submit in c??
cannot submit in c it says
We have enabled C language
We have enabled C language for this problem.
Getting WA even after trying
My submition:1067914 It
Dont know how to calculate
#include int main() { long
i dont understand what z
I think the max.m array size
brute force not efficient in
Does erastosthenes with
@admin what is wrong with
Hints to this
@admin: what happens when m=n
@admin: is it not possible to
@admin: my solution gives
I am getting TLE...How can i
Just moved from TLE to
Hi Please tell me what's the
@admin : i gave a test case
Can somebody help me? I'm
In my machine execution time
somebody help me...pgm fine
somebody help me...pgm fine
**************SigSegv error.
hint: Sieve of Eratosthenes.
import
prog.c: In function ‘main’:
import java.io.*; class
sigsev error pls help!!!!
import
Please help with my solution.
why only ada is allowed?
I am totally frustrated .. i
what will be the output if
what will be the output if
i m using Sieve of
finally solved in 2 days,
#include int main(void) { int
Can some one look at my code
can any one plz chck my code
Hey my program is working
Hey my program is working
@b1pradeep43 use the sieve of
I've implemented segmented
@redasus : maybe you need an
Sir TLE plz Help
i m using x%6==1 or x%6==5
i m beginner... i code it
My code is running under 3
my code was giving exceeded
@admin please help me i am
my code please help me adim
my code please help me adim
please some one help me it is
@admin i have used only two
ayank you need a faster
i don't understand why m
i have tried many test cases,
If i use cin and cout
i tried my own version of
Could anyone explain why my
Damn, I hate primes. :( The
Finally understood the
I hope Sieve of Eratosthenes
you can find the solution
I m getting SIGABRT error for
https://www.codechef.com/view
The same code which I
Come on CodeChef...none of my