you should try sieve of eratosthenes http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
there are far more efficient algorithms but i think this shoild be a good one to start with . ( even i got AC with this one :) ) On Fri, Mar 18, 2011 at 10:11 PM, samby <[email protected]> wrote: > The problem goes like this : > Peter wants to generate some prime numbers. Your task is to generate > all prime numbers between two given numbers! > > Input > The input begins with the number t of test cases in a single line > (t<=10). In each of the next t lines there are two numbers m and n (1 > <= m <= n <= 1000000000, n-m<=100000) separated by a space. > > Output > For every test case print all prime numbers p such that m <= p <= n, > one number per line, test cases separated by an empty line. > > Example > Input: > 2 > 1 10 > 3 5 > > Output: > 2 > 3 > 5 > 7 > > 3 > 5 > > > > the following is my code : > int main() > { > int t,trialdiv,a1,b1,i,j,candidate,flag,a[10],b[10]; > scanf("%d",&t); > for(i=0;i<t;i++) > { > scanf("\n%d %d",&a[i],&b[i]); > } > for(i=0;i<t;i++) > { > a1=a[i]; b1=b[i]; > for(candidate=a1;candidate<=b1;candidate++) > { > flag=1; > for(trialdiv=2;(trialdiv*trialdiv)<=candidate;trialdiv++) > { > if((candidate % trialdiv) == 0) > { > flag = 0; > break; > } > } > if(flag==1 && candidate != 1) > printf("\n%d",candidate); > } > > printf("\n"); > } > return 0; > } > > I AM GETTING TIME LIMIT EXCEEDED. CAN ANYBODY HELP ME WITH AN > EFFICIENT ALGORITHM ?? > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Regards Anurag Atri -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
