Project Euler - Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Solution

I couldn't use the AllPrimes function I had developed for some other Project Euler problems since the maximum array size in VB ( 2³¹-1) is not large enough for the number in this problem.  Luckily, the number under consideration has less than 15 significant digits and hence it will fit in a Double data type.

So, I wrote a long overdue routine 'IsPrime,' which returns True if a number is a prime number.  The code below ran in about 0.08 seconds on my laptop.

Option Explicit

Function IsPrime(aNbr As Variant) As Boolean
    Dim K As Long
    K = 1
    If aNbr Mod 2 = 0 Or aNbr Mod 3 = 0 Then IsPrime = False: Exit Function
    Do While 6 * K - 1 < Sqr(aNbr)
        If aNbr Mod (6 * K - 1) = 0 Or aNbr Mod (6 * K + 1) = 0 Then _
            IsPrime = False: Exit Function
        K = K + 1
        Loop
    IsPrime = True
    End Function

Sub Euler003()
    Dim aNbr As Double: aNbr = 600851475143
    'aNbr = CDec(999999)
    Dim I As Double, ProcTime As Single
    ProcTime = Timer
    I = CDec(Int(Sqr(aNbr)))
    Do While I > 1
        If aNbr / I = Int(aNbr / I) Then If IsPrime(I) Then Exit Do
        I = I - 1
        Loop
    Debug.Print I, Timer - ProcTime
    End Sub