Can any one please help me to optimize the sieve to find the primes upto 10^8 ? I want very efficient algorithm to find all primes till 10^8 for cryptsystem. i have implemented the naive sieve which is taking too much time. please sgare some classic approach with me. i will be thankful to u. thanks .
nitin1 15 Master Poster
Adak 419 Nearly a Posting Virtuoso
That is a LOT of primes! ;)
You were using the simple "test by mod" for a remainder, before?
Before I suggest something, give me:
1) info about your time requirements. Is there a time limit of some kind?
2) info about the system that is running this program. What cpu and compiler will be running this program.
When you print("%d",sizeof(int)), what do you get?
Because there are several algorithms for this, and each of them favors certain searches for primes, over others.
I'm guessing (just a guess), that the Sieve of Eratotheneis is a good choice, but we'll see.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.