FAST Sieve of Eratosthenes

This code has been declared by its author to be Public Domain code.

FAST Sieve of Eratosthenes by Andy_A

2006

Find prime numbers smaller than 16,000,000 in a flash. (Less than 2 seconds on a 1Ghz system)

Option to print the primes to screen included. Do NOT print out the prime numbers greater than 50,000 unless you want to tie up your computer for a long time. Suggest writing to text file for large primes.

;Fast Sieve of Eratosthenes
;Andy Amaya
;Nov 16,2006


	Print "Sieve of Eratosthenes"
	Print ""

	limit% = 16000000 ;Sixteen million
	
	If limit >= 16000000 Then limit = 16000000

	st% = MilliSecs()
	Dim prime%(limit)
	prime(1) = 1
	For n% = 4 To limit Step 2
		prime(n) = 1
	Next 
	For n = 3 To Sqr(limit) Step 2
		If prime(n) = 0 Then
			inc% = n+n
			i% = n*n
			While i <= limit
				prime(i) = 1
				i = i + inc
			Wend
			
		End If
	Next
	et = MilliSecs()-st
	
	
	For n = 1 To limit
		If prime(n) = 0 Then pcount% = pcount + 1
	Next




;================================================
; set showPrimes to 1 to print out primes in rows
showPrimes% = 0
numPerRow% = 10  ;ten primes per row
;************************************************
;*******  DO NOT USE WITH LARGE NUMBERS!  *******
;************************************************

;================================================
If showPrimes = 1 Then
	count = 1
	For n = 1 To limit
		If prime(n) = 0 Then
			count = count + 1
			If count <= numPerRow Then
				temp$ = temp$ + Str(n)+", "
			Else
				temp$ = temp$ + Str(n)
				Print temp$
				temp$ = ""
				count = 1
			End If
		End If
	Next
	If count < numPerRow Then
		Print temp$
	End If
End If
;================================================

	Print "There are "+pcount+" primes between 1 and "+limit
		
	
	Print ""
	Print "ET = "+et+" milliseconds"
	Print ""
	a$ = Input("Press [Enter] to Exit")

Comments

Subirenihil

2006

Seems to generate a variety of errors when I set limit up higher. Some numbers are ok, others are not.

But other than that it's by far the best I've seen.

I thought my method was fast - 10,000,000 primes in 30 minutes on a 3.2Ghz
yours blew that out of the water - 11,000,000 primes in 40 seconds

Andy_A

2006

What kind of errors do you encounter?

What's the largest number you have "sieved" through?
I'm guessing that finding 11 million primes would suggest sieving through approx. 170 million numbers.

I've never gone beyond sieving 64,000,000 numbers due to lack of patience. My system only has 512M of memory so the program starts using virtual memory (hard drive) and takes forever to calculate.

Subirenihil

2006

MAV, array index out of bounds, and I forget what others.
Sorry to get you worried - I found out that I had added an extra zero. I think some of the errors were cause because it tried to create an array larger than the array size limit and/or tried to sieve through 2,000,000,000 numbers. The only time I see a problem is if I set it to sieve through more numbers than I have memory for (RAM + virtual) or more than the maximum size of an array.

I also found that when I had run the test for the 11,000,000 primes I had run it in debug. My prime finder was run without debug.
New test comparison:
Mine: 10,000,000 primes in 30 minutes (give or take 5 minutes, I never actually timed it very accurately)
Yours: 10,000,000 primes in 9.8 seconds (give or take .05 seconds)

10,000,000 primes involves sifting through 179,424,673 numbers (179,424,673 is the ten-millionth prime number)

The previous score of 40 seconds for 11,000,000 primes should be ignored - it was in debug mode (It's actually a little more than 11,000,000 primes because I sieved through 200,000,000 numbers. The real number is 11,078,937)

My program has text that tells how many primes it finds. (no, the text is not slowing it down significantly. It gets updated once per second)

My system has 1GB of RAM and a 3.2Ghz processor.

As a side note, with my program I let it run for awhile and it found over 68,000,000 primes (at that point there's approximately 1 prime in every 19 numbers). I forget how long it took - I think somewhere about 8 hours. Because I had it save the information to my harddrive at the end, I had a 250MB list of primes. With your program, it starts using virtual memory when I start going higher than 250,000,000.

Andy_A

2006

Thanks for the info, I had thought that it would be a memory/array bounds issue.

This routine was optimized for speed so it's a real memory hog, but can be toned down a bit for better memory usage and some reporting like your routine.

Does BlitzMax support 64 bit integers? That would be the next best thing to having a large number math library.

Thanks again sharing the results you have achieved.

Subirenihil

2006

I'm going to try to optimize your code for memory usage. By using a bank instead of an array I can use only 1 byte per number rather than 4. Somewhat more sophisticated would be to use a single bit to store whether a number is prime or not. But that would involve masks and take a little more processing power - takes a little longer but 32 times as high. I'm not sure if I want to try it.

For large number math, I have coded and tested a calculator that uses strings for the numbers. I have the four basic function - addition, subtraction, multiplication, and division. It can handle 150 digit decimal numbers (it can handle any number that can be written as a decimal in a blitz string, the 150 digits is just a limit to prevent repeating decimals from be calculated to infinity). But because strings are not designed for calculation it is a slow calculator. I am going to attempt to transfer it so that it uses banks instead of strings - faster calculation and less memory usage.

_PJ_

2009

FOr greater optimisation, While/Wend is faster than For/Next or Repeat/Until.

Code Archives Forum