THE MAGAZINE FOR COMPUTER APPLICATIONS
Circuit Cellar Online offers articles illustrating creative solutions
and unique applications through complete projects, practical
tutorials, and useful design techniques.

LETıS PLAY A GAME

Sieve of Eratosthenes
by George Martin

Start ı Remember the Sieve ı Testing 2, 4ı ı Try, Try Again ı Sources and PDF

TESTING 2, 4ı

Now, letıs talk about the test. If you have a candidate for a prime number, you need to test against all numbers from two to the square root of that candidate. The square root when squared would be the candidate, so any larger number would square to larger than that candidate. Also, there is an integer divide in the CPU, so letıs look at the C-languageıs percent operator and see if we get a medal or get buried (see Listing 2).

Listing 2 tests all the prime numbers found as divisors for the candidate. If any divide is without a remainder, then the candidate is not a prime. The testing for primes starts at the number five and goes to LAST_NUMBER, another constant that you can alter for testing.

There is a square root function but only one for each candidate. It costs more but saves a lot in testing. Youıll also notice a variable LastPrime. I did that for safety, but Iım not sure if itıs needed. If this works, Iıll investigate further.

The code for the percent operator is compiled as:

66: if (i%PrimeFound[j] == 0) { /* % is mod is divide and return remainder */
00401138 8B 4D F0 mov ecx,dword ptr [j]
0040113B 8B 45 F4 mov eax,dword ptr [i]
0040113E 33 D2 xor edx,edx
00401140 F7 34 8D A0 B6 41 00 div eax,dword ptr [ecx*4+41B6A0h]
00401147 85 D2 test edx,edx
00401149 75 09 jne main(0x00401154)+144h

All in all, this is not so bad. A couple of movesıan xor (which zeros out the high part of the 64-bit divisor), the div instruction, and a test.

This program can run in a DOS window and pipe its output to a file. That file would then be the primes that have been found. I did that for the program Iıve discussed so far and got a file with the last entries as follows:

78497 999979
78498 999983

So, 999,979 and 999,983 are prime numbers. And, there are 78,498 prime numbers from 1 to 1,000,000. (In fact, one of the web references confirms that result.) However, this program takes a while to run. I canıt be doing this all day; Iıve got work to do.

PREVIOUS • NEXT