Largest prime factor

RSS

Modified: 2008/12/24 01:19 by admin - Categorized as: Samples

Problem 3

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

What is the largest prime factor of the number 600851475143?

composite = 600851475143
maxFactor = Math.Floor(Math.SquareRoot(composite))
TextWindow.WriteLine("MaxFactor = " + maxFactor)
TextWindow.WriteLine("Computing max prime factor...")

' Get odd value
If Math.Remainder(maxFactor, 2) = 0 Then
  maxFactor = maxFactor + 1
EndIf

For i = maxFactor To 3 Step -1
  If Math.Remainder(composite, i) = 0 Then
    CheckPrime()
    If isPrime = "True" Then
      Goto EndProgram
    EndIf
  EndIf
EndFor

EndProgram:
TextWindow.WriteLine("Max Prime Factor = " + i)

Sub CheckPrime
  isPrime = "True"
  
  For j = 2 To Math.SquareRoot(i)
    If Math.Remainder(i, j) = 0 Then
      isPrime = "False"
      Goto EndLoop
    EndIf
  EndFor
EndLoop:
 
EndSub