actually , I want to write a code in which i want to find prime numbers upto 10^8 higher. Can you tell me any property of prime which can tell a particular number prime or not in the most efficient way ? my purpose is to find all prime up to 10^8. thanks if u can help me in this.
Primality test - Wikipedia, the free encyclopedia
and that page has a link to this page AKS primality test - Wikipedia, the free encyclopedia
If you're doing a big block of numbers though perhaps some sort of sieve would be best.
Generating primes - Wikipedia, the free encyclopedia
There are probably more clever ways, but the "Sieve of Eratosthenes" should work. And it's very easy to code.
A simple program would require an array of 10^8 items, each with a 4 byte integer and a 1 byte flag (to check if the integer had been "hit"). That's 5 x 10^8 bytes, so would require about about 500 Megabytes of RAM. That's doable on most PCs. If that's too large, then you could shrink it by about 20% by making it a 1 bit flag (and likely writing more complicated code - it depends on the capabilities of the language you're using). If that's still too large, then you'd need to read/write to a file during the processing. Such file ops are a big performance hit, and so should be coded with some care - the reads and writes should both be done in big "chunks".
Also, remember that to determine if a number is prime or not requires only looking at its potential divisibility by integers up to the square root of the number. In your case, you'd only need to check for divisibility by primes up to 10^4.
The links in atutor's post can point you to other methods (one's which I'm unfamiliar with) that might better serve your needs.
For speeding up the Sieve of Eratosthenes, other than seeing how you're writing the code, I can give a few suggestions (though you might have already used them).
1) Use a compiled language, C, C++, maybe even Assembly given how simple the routine is. Java and .NET have a lot of overhead for computationally intensive code.
2) When you come to a new integer to "sieve with", if it's already been flagged as a composite integer, then you don't need to do it, and can skip to the next one.
3) Since any composite has already been flagged as such by the time you've gotten to a prime greater than its square root, you can always start your process at a number squared. In other words, say you're about to "sieve" using the prime 79. You don't need to start at 79 x 2. You should start checking at 79x79, then 79 x 80, then 79 x81, etc.. I don't think this will make a big difference, but it will help.
4) You could write code that saves and loads the sieve process at various stages of completion. You'd certainly want to consider this if the running time was much more than several hours. It would suck to have your computer crash or the power go out and lose all that work.
5) When things become computationally demanding, understanding your compiler is important. Two different ways of writing "the same thing" - even if they seem like they should be "the same" in performance - might turn out to be noticably different in performance when your routine is running for hours and hours. Do you declare a variable inside a loop or outside of it for best performance? These kinds of little things that we usually ignore start to really matter when the numbers get this big.
6) Shut down all other non-essential programs & services while this is running. Certainly kill your internet connection. Don't let anything annoying like your virus checker start a pre-scheduled scan.
Remember that the number of "hits" - identifications of a composite as such for the first time - will decrease as the algorithm proceeds. The code to flag as a composite will therefore be skipped much more often as the routine runs. When you start with 2, that code fires for half the numbers up to 10^8. At 3, it only executes for 1/6 the numbers up to 10^8. Again, this is relatively minor, but between this and, when "sieving on p", starting at p-squared rather than px2, it should run slightly faster the values become greater.
Put a timer in your code, and see how long it took you to reach (for sieving) the prime 101 (this is while checking through all numbers up to 10^8). The total time will be, roughly, 100 times longer (remember that you'll stop when you hit 10^4). If it takes an hour, then expect the total run to be 100 hours = 4+ solid days. If it takes 5 minutes, then the total run time will be about 8 hours.
  |
2Thanks
LinkBack URL
About LinkBacks
Originally Posted by nitin1 
