Joseph Jude

Technology, Psychology, and Story Telling

Largest prime factor of the number 600851475143

Posted: Tags: code,euler,swift,tsc,python

What I learnt (WIL): recursion & coding in non-recursive way

Logic: Ref: https://www.mathsisfun.com/prime-factorization.html "Prime Factorization" is finding which prime numbers multiply together to make the original number

Logic: Use the example in the above site Start with 2 as prime divide the given number if divisible, divide the quotient again with the prime if not divisible, increase the prime and divide the number with the prime repeat until you reach 1 the prime is the largest prime factor of the given number

Ex: 3 largest prime factor of 12 7 largest prime factor of 147 17 is itself the prime factor since it is a prime 6857 largest prime factor of 600851475143

Python

Using recursion

import sys
sys.setrecursionlimit(10000)

def findLargestPrimeFactorOf(number, currentPrime = 2):
  if number <= 1:
    return currentPrime

  if number % currentPrime == 0:
    return findLargestPrimeFactorOf(number / currentPrime, currentPrime)
  else:    
    return findLargestPrimeFactorOf(number, currentPrime + 1)


print(findLargestPrimeFactorOf(600851475143))

Without recursion:

p = 2
n = 600851475143

while n > 1:
  if n % p == 0:
    n = n / p
  else:
    p = p + 1

print p

Typescript

var p = 2;
var n = 600851475143;

while (n > 1){
  if (n % p == 0) {
    n = n / p;
  } else {
    p = p + 1
  }
}

console.log(p);

Swift

With recursion:

var currentPrime = 2

func findLargestPrimeFactorOf(number: Int) -> Int {
  if number <= 1 {
    return currentPrime
  }

  if number % currentPrime == 0 {
    return findLargestPrimeFactorOf(number / currentPrime)
  } else {
    currentPrime += 1
    return findLargestPrimeFactorOf(number)
  }
}

print(findLargestPrimeFactorOf(600851475143))

Without recursion:

var currentPrime = 2
var numberToFactor = 600851475143

while numberToFactor > 1 {
  if numberToFactor % currentPrime == 0 {
    numberToFactor = numberToFactor / currentPrime
  } else {
    currentPrime += 1
  }
}

print(currentPrime)

Git Repository / All Euler Solutions

Got comments? Tweet it, or comment below.


Comments

comments powered by Disqus