Generate Primes over 100 Million
Hello, I salvaged the following piece of code from:
http://www.vbforums.com/showpost.php...65&postcount=8
This code works fine, but the problem comes when I need to get all the primes above 100 million. I am familar (at least a little bit) with the BigInteger class in .NET 4.0, but when I replace all the instances of "Integer" with "BigInteger" in the following code I get this error:
Value of type 'System.Collections.Generic.List(Of System.Numerics.BigInteger)' cannot be converted to 'System.Collections.Generic.List(Of Integer)'.
(The reason I need primes above 100 million is that I'm trying to work through some projects on www.projecteuler.net)
Anyone have some ideas on how to modify the code to work with BigIntegers, Thank you very much for your help. If you need more code examples please ask.
vb.net Code:
'Sieve of Eratosthenes
'http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
'1. Create a contiguous list of numbers from two to some highest number n.
'2. Strike out from the list all multiples of two (4, 6, 8 etc.).
'3. The list's next number that has not been struck out is a prime number.
'4. Strike out from the list all multiples of the number you identified in the previous step.
'5. Repeat steps 3 and 4 until you reach a number that is greater than the square root of n (the highest number in the list).
'6. All the remaining numbers in the list are prime.
Private Function Sieve_of_Eratosthenes(ByVal MaxNum As Integer) As List(Of Integer)
'tested to MaxNum = 10,000,000 - on 1.8Ghz Laptop it took 1.4 seconds
Dim thePrimes As New List(Of Integer)
Dim toNum As Integer = MaxNum, stpw As New Stopwatch
If toNum > 1 Then 'the first prime is 2
stpw.Start()
thePrimes.Capacity = toNum 'size the list
Dim idx As Integer
Dim stopAT As Integer = CInt(Math.Sqrt(toNum) + 1)
'1. Create a contiguous list of numbers from two to some highest number n.
'2. Strike out from the list all multiples of 2, 3, 5.
For idx = 0 To toNum
If idx > 5 Then
If idx Mod 2 <> 0 _
AndAlso idx Mod 3 <> 0 _
AndAlso idx Mod 5 <> 0 Then thePrimes.Add(idx) Else thePrimes.Add(-1)
Else
thePrimes.Add(idx)
End If
Next
'mark 0,1 and 4 as non-prime
thePrimes(0) = -1
thePrimes(1) = -1
thePrimes(4) = -1
Dim aPrime, startAT As Integer
idx = 7 'starting at 7 check for primes and multiples
Do
'3. The list's next number that has not been struck out is a prime number.
'4. Strike out from the list all multiples of the number you identified in the previous step.
'5. Repeat steps 3 and 4 until you reach a number that is greater than the square root of n (the highest number in the list).
If thePrimes(idx) <> -1 Then ' if equal to -1 the number is not a prime
'not equal to -1 the number is a prime
aPrime = thePrimes(idx)
'get rid of multiples
startAT = aPrime * aPrime
For mltpl As Integer = startAT To thePrimes.Count - 1 Step aPrime
If thePrimes(mltpl) <> -1 Then thePrimes(mltpl) = -1
Next
End If
idx += 2 'increment index
Loop While idx < stopAT
'6. All the remaining numbers in the list are prime.
thePrimes = thePrimes.FindAll(Function(i As Integer) i <> -1)
stpw.Stop()
Debug.WriteLine(stpw.ElapsedMilliseconds)
End If
Return thePrimes
End Function
And here is what I changed it to:
vb.net Code:
Private Function Sieve_of_Eratosthenes(ByVal MaxNum As BigInteger) As List(Of BigInteger)
'tested to MaxNum = 10,000,000 - on 1.8Ghz Laptop it took 1.4 seconds
Dim thePrimes As New List(Of BigInteger)
Dim toNum As BigInteger = MaxNum, stpw As New Stopwatch
If toNum > 1 Then 'the first prime is 2
stpw.Start()
thePrimes.Capacity = toNum 'size the list
Dim idx As BigInteger
Dim stopAT As BigInteger = Math.Sqrt(toNum) + 1
'1. Create a contiguous list of numbers from two to some highest number n.
'2. Strike out from the list all multiples of 2, 3, 5.
For idx = 0 To toNum
If idx > 5 Then
If idx Mod 2 <> 0 _
AndAlso idx Mod 3 <> 0 _
AndAlso idx Mod 5 <> 0 Then thePrimes.Add(idx) Else thePrimes.Add(-1)
Else
thePrimes.Add(idx)
End If
Next
'mark 0,1 and 4 as non-prime
thePrimes(0) = -1
thePrimes(1) = -1
thePrimes(4) = -1
Dim aPrime, startAT As BigInteger
idx = 7 'starting at 7 check for primes and multiples
Do
'3. The list's next number that has not been struck out is a prime number.
'4. Strike out from the list all multiples of the number you identified in the previous step.
'5. Repeat steps 3 and 4 until you reach a number that is greater than the square root of n (the highest number in the list).
If thePrimes(idx) <> -1 Then ' if equal to -1 the number is not a prime
'not equal to -1 the number is a prime
aPrime = thePrimes(idx)
'get rid of multiples
startAT = aPrime * aPrime
For mltpl As BigInteger = startAT To thePrimes.Count - 1 Step aPrime
If thePrimes(mltpl) <> -1 Then thePrimes(mltpl) = -1
Next
End If
idx += 2 'increment index
Loop While idx < stopAT
'6. All the remaining numbers in the list are prime.
thePrimes = thePrimes.FindAll(Function(i As BigInteger) i <> -1)
stpw.Stop()
Console.WriteLine(stpw.ElapsedMilliseconds & " milliseconds to generate primes")
End If
Return thePrimes
End Function
Re: Generate Primes over 100 Million
did you also change the instances of "Integer" to "BigInteger" in line 9?
Re: Generate Primes over 100 Million
yup, I also updated first post to show what I have (should have done it before but I didn't think of it)
(at the top I also have)
vb.net Code:
Imports System.Math
Imports System.Numerics
Here is a custom class I wrote before finding the above code, it works, but is way too slow.
vb.net Code:
Class Primes
Dim LargestNonPrime As ULong = 0 ' Will only generate primes below this number
Dim primes As New ArrayList ' Will hold all our primes
Dim currentprime As Long = -1 ' set to -1 so that you will return the first prime in the array (0) because you have to iterate the currentprime b4 you can return the value
Dim toRemove As New ArrayList ' will hold the numbers to remove from our primes array (holds non-primes)
Sub Generate(ByVal tempnum As ULong)
LargestNonPrime = tempnum
Dim sw As New Stopwatch 'If you want to benchmark, uncomment this and the next line
sw.Start()
For x As Integer = 0 To LargestNonPrime ' Creates an arraylist from 0 to the number you specify
primes.Add(x)
Next
For i As Integer = 2 To LargestNonPrime / 2
Dim x As BigInteger = BigInteger.Multiply(i, i) ' Replace with Dim x as ulong = i*i if you are not running .NET 4.0 (imports system.numerics is required)
While x <= LargestNonPrime
toRemove.Add(x) 'adds all numbers that are non-prime into an array for removal
x += i
End While
Next
primes.Remove(0) 'manually remove 0 and 1 from the array (IF you count 1 as a prime number, then comment out or remove the next line)
primes.Remove(1)
toRemove.Sort() 'sorts the array from smallest to largest (when adding items to the array we have a LOT of doubles (when i was testing all primes for 100,000 i had close to .5million items in this array.
'remove doubles from toRemove array
For i = toRemove.Count - 1 To 1 Step -1
If (toRemove(i).ToString() = toRemove(i - 1).ToString()) Then
toRemove.RemoveAt(i)
End If
Next
'next 3 lines were used for debugging purposes
'For x As Integer = 0 To toRemove.Count - 1
' Console.WriteLine(toRemove(x).ToString)
'Next
For i As Integer = 0 To toRemove.Count - 1
primes.Remove(CInt(toRemove(i).ToString)) 'removes all of the items in the remove array from the array of primes we have going (leaves only primes left)
'Console.WriteLine(toRemove.Count.ToString & " left to remove, removing " & toRemove(i).ToString) 'used for debugging purposes
Next
'rest of the subroutine used for debugging purposes
sw.stop()
Console.WriteLine("ran in: " & sw.ElapsedMilliseconds & " number of primes: " & primes.Count)
'For x As Integer = 0 To primes.Count - 1
' Console.WriteLine(primes(x).ToString)
'Next
End Sub
Sub Reset()
currentprime = -1 'resets our current prime to -1 (so when we call .NextPrime() it will return the first value in the array
End Sub
Function NumOfPrimes() As ULong
Return primes.Count ' returns the number of primes we have...
End Function
Function NextPrime() As ULong
currentprime += 1 'since we set currentprime = -1 at the beginning and in the .Reset() sub it will add 1 making it equal to 0 and thus return the first item in the array of primes
Return primes(currentprime)
End Function
End Class
