Ooops
January 26, 2021, 12:47:57 PM

### Author Topic: [bb] FAST Sieve of Eratosthenes by Andy_A [ 1+ years ago ]  (Read 534 times)

#### BlitzBot

• Jr. Member
• Posts: 1
##### [bb] FAST Sieve of Eratosthenes by Andy_A [ 1+ years ago ]
« on: June 29, 2017, 12:28:39 AM »
Title : FAST Sieve of Eratosthenes
Author : Andy_A
Posted : 1+ years ago

Description : 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.

Code :
Code: BlitzBasic
1. ;Fast Sieve of Eratosthenes
2. ;Andy Amaya
3. ;Nov 16,2006
4.
5.
6.         Print "Sieve of Eratosthenes"
7.         Print ""
8.
9.         limit% = 16000000 ;Sixteen million
10.
11.         If limit >= 16000000 Then limit = 16000000
12.
13.         st% = MilliSecs()
14.         Dim prime%(limit)
15.         prime(1) = 1
16.         For n% = 4 To limit Step 2
17.                 prime(n) = 1
18.         Next
19.         For n = 3 To Sqr(limit) Step 2
20.                 If prime(n) = 0 Then
21.                         inc% = n+n
22.                         i% = n*n
23.                         While i <= limit
24.                                 prime(i) = 1
25.                                 i = i + inc
26.                         Wend
27.
28.                 End If
29.         Next
30.         et = MilliSecs()-st
31.
32.
33.         For n = 1 To limit
34.                 If prime(n) = 0 Then pcount% = pcount + 1
35.         Next
36.
37.
38.
39.
40. ;================================================
41. ; set showPrimes to 1 to print out primes in rows
42. showPrimes% = 0
43. numPerRow% = 10  ;ten primes per row
44. ;************************************************
45. ;*******  DO NOT USE WITH LARGE NUMBERS!  *******
46. ;************************************************
47.
48. ;================================================
49. If showPrimes = 1 Then
50.         count = 1
51.         For n = 1 To limit
52.                 If prime(n) = 0 Then
53.                         count = count + 1
54.                         If count <= numPerRow Then
55.                                 temp\$ = temp\$ + Str(n)+", "
56.                         Else
57.                                 temp\$ = temp\$ + Str(n)
58.                                 Print temp\$
59.                                 temp\$ = ""
60.                                 count = 1
61.                         End If
62.                 End If
63.         Next
64.         If count < numPerRow Then
65.                 Print temp\$
66.         End If
67. End If
68. ;================================================
69.
70.         Print "There are "+pcount+" primes between 1 and "+limit
71.
72.
73.         Print ""
74.         Print "ET = "+et+" milliseconds"
75.         Print ""
76.         a\$ = Input("Press [Enter] to Exit")

Subirenihil(Posted 1+ years ago)

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.2Ghzyours blew that out of the water - 11,000,000 primes in 40 seconds

Andy_A(Posted 1+ years ago)

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(Posted 1+ years ago)

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(Posted 1+ years ago)

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(Posted 1+ years ago)

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_(Posted 1+ years ago)

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