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.