Largest prime factor of a composite number

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

Prime factors are prime numbers that can be multiplied together to make a given number. One way to find them is to start by dividing the number by the first prime (2) and continuing to do so until it cannot be divided, then moving on to the next.

Module Module1
  Sub Main()
    Dim beganAt As Date = Now
    Dim n As Long = 600851475143
    Dim factor As Integer = 2
    Dim highestFactor As Integer = 1
    While n > 1
      If n Mod factor = 0 Then
        highestFactor = factor
        n = n / factor
        While n Mod factor = 0
          n = n / factor
        End While
      End If
      factor = factor + 1
    End While
    Dim endAt As Global.System.TimeSpan = Now.Subtract(beganAt)
    Dim took As Integer = endAt.Milliseconds
    Console.WriteLine(highestFactor.ToString + " in " + took.ToString + "ms.")
    Console.ReadKey()
  End Sub
End Module
This entry was posted in Coding, Computing, Open University and tagged , , , . Bookmark the permalink.