Another Prime Generator problem(time exceeded)

[baronpampa]

Hello!
I'd like to ask you for help in solving this problem. I've written a code using the Sieve of Erastotenes, but, obviously, it's too slow. Could anyone explain me what have I done wrong? I must ask you for patience, as I'm new to programming (and probably my English isn't perfect).

include <iostream>
using namespace std;
int main()
{
   unsigned short t;
   unsigned int x;
   cin>>t;
   unsigned int * m=new unsigned int[t*2];              //Table m saves the borders of the interval
   for(int j=0;j<t*2;j++)
        cin>>m[j];                                      //Borders are inserted
   for(unsigned short j=0;j<t;j++)
   {x=1+m[1+2*j]-m[2*j];                                //Var x remembers how many numbers are there to be analysed
   bool * p = new bool[x];                              //Table x remembers whether a number is prime or not(true stands for prime)
   for(unsigned int u=0;u<x;u++)
   {p[u]=true;                                          //At the beggining all numbers are considered to be prime
   }
   p[0]=0;
   p[1]=0;
   for(unsigned int k=m[2*j];k<=m[1+2*j];k++)           //In this loop numbers are analysed
    {
        {if(k%2==0 and k!=2)                            //1 isn't a prime number. 2 is a prime number. And every even number isn't prime
            {p[k-m[2*j]]=0;}
        else
        for(unsigned short l=3;l*l<=k;l=l+2)            //I find numbers which aren't prime using the Sieve of Erastotenes
            {if (k%l==0)
            {
            p[k-m[2*j]]=false;
            break;
        }
            }}
    }
    for(unsigned int k=m[2*j];k<=m[1+2*j];k++)          //And cout every prime number from the given interval
    {if(p[k-m[2*j]]==true)
        cout<<k<<endl;}
   if(j!=t*2-1)
    cout<<endl;
   }
    return 0;
}

[leppyr64]

Your bracketing and indenting is a little inconsistent, which was awkward. Sometimes you indent 4 spaces and sometimes 5.

Why are you doing this?:

p[0]=0;
p[1]=0;

p[0] and p[1] do not correspond to 0 and 1, they correspond to m[2*j] and m[2*j]+1, correct?

As a general rule, cin and cout are slow and should be avoided in favour of scanf and printf, unless you turn syncing with stdio off. (I don't do it, so can't tell you how or if it's faster)

[baronpampa]

Thank you! This helps a lot, as the program is two times faster(at least it is on my computer). Unfortunately it's not enough - could I ask for more advices?
I've tried to make it easier to read - does it make any difference?

#include <iostream>
#include<cstdio>
using namespace std;
int main()
{
    unsigned int t;
    unsigned int x;
    scanf("%u", &t);
    unsigned int * m=new unsigned int[t*2];                       //Table m saves the borders of the interval
    for(int j=0;j<t*2;j++)
        scanf("%d", &m[j]);                                      //Borders are inserted
    for(unsigned short j=0;j<t;j++)
    {cout<<endl;
        x=1+m[1+2*j]-m[2*j];                                      //Var x remembers how many numbers are there to be analysed
    bool * p = new bool[x];                                       //Table x remembers whether a number is prime or not(true stands for prime)
    for(unsigned int u=0;u<x;u++)
    {p[u]=false;                                                  //At the beggining all numbers are not considered to be prime
    }
    for(unsigned int k=m[2*j];k<=m[1+2*j];k++)                    //In this loop numbers are analysed
    {
        switch(k)
    {case 2:
    p[k-m[2*j]]=true;
    break;
    case 3:
    p[k-m[2*j]]=true;
    break;
    case 5:
    p[k-m[2*j]]=true;
    break;
    case 7:
    p[k-m[2*j]]=true;
    break;
    default:
    {if(k%2==0 and k!=2)
        {p[k-m[2*j]]=0;}
    else
        for(unsigned short l=3;l*l<=k;l=l+2)                 //I find numbers which aren't prime using the Sieve of Erastotenes
        {if (k%l==0)
            {
            p[k-m[2*j]]=false;
            break;
            }
        p[k-m[2*j]]=true;
        }
    }
    }
}
for(unsigned int k=m[2*j];k<=m[1+2*j];k++)                   //And cout every prime number from the given interval
    {if(p[k-m[2*j]]==true)
    printf("%u\n", k);
    }
   }
    return 0;
}

[leppyr64]

For how many iterations of the loop will k be equal to {2,3,5,7}? Is it really worth the extra overhead of checking them for the other 10000 numbers that you will iterate over? Every second number is going to be divisible by two, can you think of a way to remove it so that you don't have to check divisibility by two on every iteration as well as your general check?

As a general note, input is read from stdin and output is printed to stdout. You don't need to read all of the test cases and then output all of them. You can read one test case, print output, read the second test case, and so on.

[baronpampa]

Sorry for keeping you busy by asking so many questions. I`m really trying to do it on my own...but it doesn't want to work.
I've upgraded the program after reading your advices. Right now there are two possible main loops, so the program has to analase only odd numbers. I've moved the switch with {2,3,5,7} further, so it's after the main loop. It won't be checked more than 10 times, I suppose it's not a problem anymore. Moreover, I've added quite a few "if's" to the printing loop-it checks whether the first number is even or odd, and whether it's not a 0,1 or 2(as these were troublesome).
The trouble is: none of these seem to work. I'm checking the program by checking the numbers from 1 to 10^7, it's still the same. I've checked the times of pure computations and pure printing by removing the main loop, then I've tried to mix the current version with the previous one. It seems that these changes just give around the same results in any combination.
I understand your post and what were the problems with previous version. I can see no mistake in my ideas nor in the implementations. Could you explain me what's wrong? Again, sorry for being so learn-proof; ). I sincerely hope it's not laziness-I've been checking it all day. Before your today's post I've thought of some things similar to your advices, but, again, changes weren't improving anything(In example, I've tried just to delete the {2,3,5,7} switch. Or eliminate the %2 in every iteration. The problem was the same as now-no changes in speed). If I should try harder before asking, say it; )

#include <iostream>
#include<cstdio>
using namespace std;
int main()
{
    unsigned int t;
    unsigned int x;
    scanf("%u", &t);
    unsigned int * m=new unsigned int[t*2];                       //Table m saves the borders of the interval
    for(int j=0;j<t*2;j++)
        scanf("%d", &m[j]);                                      //Borders are inserted
    for(unsigned int j=0;j<t;j++)
    {cout<<endl;
        x=1+m[1+2*j]-m[2*j];                                      //Var x remembers how many numbers are there to be analysed
    bool * p = new bool[x];                                       //Table x remembers whether a number is prime or not(true stands for prime)
    for(unsigned int u=0;u<x;u++)
    {p[u]=false;                                                  //At the beggining all numbers are not considered to be prime
    }
    if(m[2*j]%2!=0)
    for(unsigned int k=m[2*j];k<=m[1+2*j];k+=2)                    //In this loop numbers are analysed
    {
    {
    {
            for(unsigned int l=3;l*l<=k;l=l+2)                       //I find numbers which aren't prime using the Sieve of Erastotenes
            {if (k%l==0)
                {
                p[k-m[2*j]]=false;
                break;
                }
            p[k-m[2*j]]=true;
            }
    }
    }
    }
    else
    for(unsigned int k=m[2*j]+1;k<=m[1+2*j];k+=2)                    //In this loop numbers are analysed
    {
    {
    {
            for(unsigned int l=3;l*l<=k;l=l+2)                 //I find numbers which aren't prime using the Sieve of Erastotenes
            {if (k%l==0)
                {
                p[k-m[2*j]]=false;
                break;
                }
            p[k-m[2*j]]=true;
            }
    }
    }
    }
    if(m[2*j]<8)
{
    for(int o=0;o<8;o++)
        switch(m[2*j]+o)
    {case 2:
        p[o]=true;
        break;
    case 3:
        p[o]=true;
        break;
    case 5:
        p[o]=true;
        break;
    case 7:
        p[o]=true;
        break;}
}
if(m[2*j]==2 or m[2*j]==0)
    {   cout<<2<<endl;
    for(unsigned int k=m[2*j]+1;k<=m[1+2*j];k+=2)                   //And cout every prime number from the given interval
        {
        if(p[k-m[2*j]]==true)
        printf("%u\n", k);
        }
    }
else
if(m[2*j]%2==0)
 for(unsigned int k=m[2*j]+1;k<=m[1+2*j];k+=2)                   //And cout every prime number from the given interval
    {
    if(p[k-m[2*j]]==true)
    printf("%u\n", k);
    }
else
    if(m[2*j]==1)
{
    cout<<2<<endl;
    for(unsigned int k=m[2*j];k<=m[1+2*j];k+=2)                   //And cout every prime number from the given interval
    {
    if(p[k-m[2*j]]==true)
    printf("%u\n", k);
    }

}
else
    for(unsigned int k=m[2*j];k<=m[1+2*j];k+=2)                   //And cout every prime number from the given interval
    {
    if(p[k-m[2*j]]==true)
    printf("%u\n", k);
    }
   }
   return 0;
}

[leppyr64]

You don't bother me at all You're trying to learn and that's what's most important. I will continue asking you questions with the intention of guiding you to the right answer.

Get rid of the 2,3,5,7 stuff entirely. It makes your runtime slower (but it's not the largest problem)

Now what you call a "sieve" is not really a sieve. It's actually trial division. You check if a number is prime by checking if it's divisible by a number less than its square root. If you were using a sieve you would be flagging off multiples of every prime so that you didn't check them again.

Now lets look at your trial division. You're checking using all odd numbers up to the square root and two. Do you really need to check "all odd numbers". Could you simplify that?

[baronpampa]

Thank you very much! Task accomplished: ). I've noticed that maximum number is given in the text of the problem, it was a priceless information. I've just created a table with the first ~3500 prime numbers(from 2 to sqrt(10^9)) and then used them to check whether input is prime or not. Still, I've got a question:
I've noticed that on my computer printing numbers on the run(every time the program finds a prime it prints it immediatly) makes program much slower then creating a table with results and then printing them. Can you explain that? I thought that the former would be faster, as the program doesn't need to create additional table and run a loop.

[leppyr64]

Please post your two solutions, where the only difference is the extra table and output loop so that I can compare.

[baronpampa]

O...nevermind. It would be quite inconvenient to create an alternative version now(the working program is written from a scratch). But should I see something similar again, I'll create a new topic. Thanks for help and goodbye(...until my next question. Currently working on palindromes; ))