Sum of all the primes below two million

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

Seemed pretty straight forward, loop through all numbers up to 2,000,000 – if they’re prime add them to a tally.

Module Module1

  Sub Main()
    Dim beganAt As Date = Now
    Dim n As Integer = 2000000
    Dim total As Long = 0

    For counter As Integer = 2 To n
      If isPrime(counter) = True Then
        total = total + counter
      End If
    Next

    Dim endAt As Global.System.TimeSpan = Now.Subtract(beganAt)
    Dim took As Integer = endAt.Milliseconds

    Console.WriteLine(total.ToString + " in " + took.ToString + " ms.")
    Console.ReadKey()
  End Sub

  Private Function isPrime(ByVal thisNumber As Integer) As Boolean
    ' Prime numbers other than two are odd...
    If thisNumber = 2 Then
      Return True
    ElseIf thisNumber Mod 2 = 0 Then
      Return False
    End If

    'Check it isn't divisible by up to its square root
    '(consider n=(root n)(root n) as factors)
    For counter As Integer = 3 To (Math.Sqrt(thisNumber)) Step 2
      If thisNumber Mod counter = 0 Then
        Return False
      End If
    Next
    Return True
  End Function

End Module

Just needed to be¬†careful¬†with data types – VB.Net’s Integer isn’t large enough so I changed to a Long. Gives 142,913,828,922 in 953 milliseconds.

 

 

5 thoughts on “Sum of all the primes below two million”

  1. A small optimization is only to loop over odd numbers with a step +2. Btw, I first tried to check if a number is prime in a range 3..n/2 which was very slow. Math.Sqrt(thisNumber) turned out to be a lot lot faster for big numbers.

  2. Or in Ruby:

    class Integer
    def prime?
    return true if self == 2
    return false if self == 1 || self % 2 == 0 #Even numbers can't be prime
    1.upto(Math.sqrt(self).floor) { |n| return false if ((self % n) == 0 && (n != self) && (n != 1)) }
    true
    end
    end

    def sum_primes_in_range (r)
    sum = 0
    r.each { |n|
    if n.prime?
    sum += n
    end
    }
    sum
    end

    puts sum_primes_in_range(1...2000000)

Comments are closed.