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 then if you have not found a number that divides into evenly once reaching , 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.