The 10001st prime number

Project Euler time again, I’ve come out of sequence – here’s problem 7:

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

I’m going to start at the beginning and check if each is a prime, until I find the 10001th.

Module Module1
  Sub Main()
    Dim beganAt As Date = Now
    Dim n = 10001
    Dim prime As Integer = 0
    Dim counter As Integer = 0

    ' Check each number until you've got 10001 prime numbers.
    Do Until prime = n + 1
      counter = counter + 1
      If isPrime(counter) Then
        prime = prime + 1
      End If
    Loop

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

    Console.WriteLine(counter.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

I used a function for finding primes, it keeps coming up. It takes an integer and returns true or false by discounting even numbers except 2 and checking for divisibility up to the integer’s square root. If you consider $latex n=sqrt{n} times sqrt{n} $ then if you have not found a number that divides into $latex n$ evenly once reaching $latex sqrt{n}$, its factors can only be one and itself. This significantly reduces processing time and appears to be how my HP40gs works out its ISPRIME() function.

It gives the answer 104743 in 125 milliseconds.

This entry was posted in Coding and tagged , , , . Bookmark the permalink.

2 Responses to The 10001st prime number

  1. Nikhil says:

    I think yours is slow. I ran mine and the execution time was as follows:
    10001st Prime is 104743
    Total Execution time = 0.000000000000000
    Press any key to continue . . .

Comments are closed.