Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

SPOJ: Prime1

VinayKhareVinayKhare Posts: 69Member
Hello Everybody,

[link=https://www.spoj.pl/problems/PRIME1/]Question is to Generate all Prime Numbers between two given Numbers.[/link]

I have impleamented it number of ways....number of styles...but.....
Everytime I got the result "Time Limit Exceeded"

[code]
#include
#include

int main()
{
int a, b, c = 1, test,root,v;
scanf("%d",&test);
while(test!=0)
{
scanf("%d%d",&a,&b);
printf("
");
while(a<=b)
{
if (a==2 || a==3)
{
printf("%d
",a);
a++;
continue;
}
if ((a%2)==0 || (a%3)==0 || a<2)
{
a++;
continue;
}
root=(int)(sqrt(a)) + 1;
for(v=6;v<=root;v+=6)
{
if (a%(v-1)==0)
{
c = 0;
break;
}
if (a%(v+1)==0)
{
c = 0;
break;
}
}
if(c == 1)
printf("%d
",a);
a++;
}
test--;
}
return 0;
}[/code]

Can anyone help me speedup the code...
waiting for replies...
Thank You

Comments

  • LundinLundin Posts: 3,711Member
    How exactly do you clock the program?

    I don't really grasp how your algorithm works, but here are some general suggestions:

    Major optimization:
    printf() is incredible slow, and if you clock the whole program you will only measure how sluggish printf() is, and not the speed of the actual algorithm.

    sqrt() is also a slow function. As soon as you involve it, you involve float numbers, which are notoriously slow. Unless you have a real big amount of numbers to display, calling sqrt() will only make the program inefficient. Might be better to count from 2 to n/2 instead, even if it involves more iterations.

    Make sure you never check if even numbers are prime numbers. That is pointless.

    Minor optimization:
    for loops are generally a tiny bit more efficient than while loops. You can iterate from max down to zero too, to save a few ticks (the CPU compares against zero more efficiently than it compares against a variable number).


    (Also note that you cannot measure time accuately on hosted desktop environments like Windows and *nix, since they are not realtime systems.)
  • VinayKhareVinayKhare Posts: 69Member
    I tried to consider above stated ideas....and impleamented the following code...
    But still get the same result...
    [code]
    #include

    int main()
    {
    int test; // for Number of test cases.
    long unsigned int a,b,i,c; // a first number, b second limit
    scanf("%d",&test);
    for(;test;test--)
    {
    scanf("%lu%lu",&a,&b); //we have to find prime numbers between a and b
    for(;a<=b;a+=2)
    {
    c=0; //putting c=0 number is prime else not
    if(a<2 || ( !(a%2) && a!=2) )
    a++; //if a is 1 or (even but not 2) increment by 1
    if(a==2)
    {
    printf("2
    ");
    if(b==2) //if upper limit is 2, don't print 3
    break;
    a++;
    }
    for(i=3;i<=( (a/2)+ 1);i+=2)
    {
    if(!(a%i)) //for loop is chekcing for prime upto (a/2)+1
    {
    c=1;
    break;
    }
    }
    if(!c)
    printf("%lu
    ",a); //print if c==0 else continue.
    }
    }
    }
    [/code]

    Help me, Waiting for Replies...
    Where am I slow?? This code is teasing my mind.
  • VinayKhareVinayKhare Posts: 69Member
    Hello Lundin,
    Have you read my code? Can you please tell me, where am I wrong...why the code is not being accepted at spoj.pl. Why I always get the result "Time limit exceeded".

    How could I develop the insight of creating more and more efficient algorithm.

    What to learn, what to understand???
  • arjunmayilvagananarjunmayilvaganan IndianPosts: 1Member
    edited March 30

    This was my code and i still get the Time Limit Exceeded warning for the PRIME1 problem in SPOJ: Any solutions yet?

    include<stdio.h>

    int main(void) { int i,j,k,n; long int l,a[10],b[10]; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%ld %ld",&a[i],&b[i]); } for(i=0;i<n;i++) { for(l=a[i],j=0;l<=b[i];l++,j=0) {
    k=1; while(k<=l) { if(l%k==0) j++; k++; } if((j<=2)&&(l!=1)) printf("%ld\n",l); } printf("\n"); } return 0; }

Sign In or Register to comment.