prime number

[nitin1]

hello, Can anyone please tell me the most efficient know till date so as to find the prime numbers up to 10^8 or higher. I am using sieve and using odd number optimization with it also. but it is not too much effiecent which i want. Can you please any optimization or any other way so as to calculate all prime numbers uptp 10^ 8 pr higher.

P.S I wanto calculate as i am doing project on cryptgraphy. thanks in advance if you can help me in this :-)

[Adak]

You posted this last week, and I replied with several questions, which you never answered.

1) What code are you using now? There are three different sieve algorithms for primes, which one are you using? Eratotheneis? Please post it.

2) What run times are you hoping for, and what run times are you currently getting?

I have some optimizations for the Sieve of Eratotheneis, but I'll need to run your code on my system, and time it, so I can compare it with mine, and see what optimizations will help.

[nitin1]

#define MAX 100000000

int primes[MAX/10];


void sieve()
{
      int i,j,k=0;
      int p=sqrt(MAX);

      for(i=3;i<=p;i+=2)
      {
            if(a[i]==0) 
             for(j=i*i;j<=MAX;j+=i)
             {
                    a[j]=1;
             }
      }

      primes[k++]=2;

      for(i=3;i<=MAX;i+=2)
      {
           if(a[i]==0)
           primes[k++]=i;
      }

      return;
}

This is what i am using right now, i want to optimize it more. how can i ? It is the code which i was talking about. thanks.

[Adak]

I'll test it out, after I get some zzz's. When you print out sizeof(int), what number do you get on your system?

[nitin1]

lol. it's 4 bytes. ;)

[Adak]

That's a good program. I can improve it only a small amount.

Here's my question: Once you generate these thousands of primes, you can refer to them over and over again, for your cryptography program - you only have to find the primes just ONCE. So the extreme emphasis on speed is a bit of a mystery.

I thought this might be for a SPOJ or Project Euler problem.

Anyway, I'm still working with it.

[nitin1]

yes, it is a spoj,codechef,UVA, interviewstreet, codeforces and many others' question. but variation of this you can get at any site. Si of you can improve , i think it will be damn helpful for me :-) thanks and yeah, i have calculated it once only.

[Adak]

In my tests, you have the fastest Sieve of Eratosthenes, while keeping it with that algorithm. I tried four different optimizations, but they did nothing to speed it up - and at least one, actually slowed it down.

Even in the IDE, your program runs in 1.77 seconds or so, on my PC. There are other ways to (maybe) make it faster, but then it becomes something else, not a Sieve of Eratosthenes program, at all.

So, take the next step, and enter it at SPOJ, in this classic problem:
http://www.spoj.pl/problems/TDKPRIME/

This is a beast of a problem, even with a good Sieve program, but we'll see if it gets accepted. (that is, if it passes the stiff time requirement, with the right answers). You have a lot of other code to add to this, to make it work correctly with the input the program needs to work with.

But it should be fun.