# 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.")
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 $n=sqrt{n} times sqrt{n}$ then if you have not found a number that divides into $n$ evenly once reaching $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.

## 2 thoughts on “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 . . .

1. Very possibly, I don’t know what we both ran it on. I suspect I used my net-book which isn’t quick.