Generate Primes over 100 Million

[patplays852]

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.

'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:

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

[Philly0494]

did you also change the instances of "Integer" to "BigInteger" in line 9?

[patplays852]

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)

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.

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