# Project Euler #3 - Largest Prime Factor

### Peter Kim Frank twitter logo github logo Jun 20 '18Updated on May 28, 2019・1 min read

Project Euler (7 Part Series)

It's been fun reading responses in the last two Project Euler threads. If you missed them, you can view Problem #1 and Problem #2.

Let's keep it rolling with Problem #3. Again, this is from the wonderful Project Euler.

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

What is the largest prime factor of the number 600851475143 ?

Look forward to seeing solutions in your language of choice!

DISCUSS (15) Ruby✨💎✨

``````require "prime"

puts Enumerator.new { |y|
n = 600851475143

Prime.each do |prime|
break if n == 1

q, r = n.divmod(prime)

next if r.nonzero?

y << prime
n = q
redo
end
}.to_a.last
``````

If we really only care about the largest prime factor, this can be simplified:

``````require 'prime'

n = 600851475143

Prime.each do |prime|
break prime if n == 1
next unless n % prime == 0
n = n / prime
redo
end
``````

It returns `2` when `n = 1`, my code returns `nil`.

True. Though more of an input validation problem since 1 has no prime factors by definition and is also not prime itself.

Haskell, simple and recursive, optimized for readability:

``````factorize :: (Integral a) => a -> [a]
factorize n = factorize' n 2 where
factorize' 1 _ = []
factorize' n factor
| n `mod` factor == 0 = factor : factorize' (n `div` factor) factor
| otherwise           = factorize' n (factor + 1)
``````

J (q: returns all prime factors of the number, {: return the tail of a list):

``````{:q:600851475143
``````

PHP, again.

Solution: 6857

``````\$input = 600851475143;
\$primeFac = getFac(\$input);
rsort(\$primeFac);
echo reset(\$primeFac);
function getFac(\$input) {
\$i = 2;
\$primeFac = array();
for (\$i = 2; \$i * \$i <= \$input; \$i++) {
if (fmod(\$input, \$i) == 0) {
\$primeFac[] = \$i;
\$input = \$input / \$i;
}
}
if (\$input != 1) {
\$primeFac[] = \$input;
}
return \$primeFac;
}
``````

Python 3 solution. Inefficient I know...

``````import math

factors = []
n = 600851475143

for i in range(2, math.ceil(math.sqrt(n))):
while n % i == 0:
factors.append(i)
n = n / i

print(factors[-1])
``````

Simple Rust solution

``````fn largest_prime(num: u64) -> u64 {
let mut a = num;
let mut b = 2;
let mut c = 0;
while a > 1  {
if a % b == 0 {
if b > c {c = b};
a /= b;
b = 2;
continue;
}
b += 1;
}
c
}

// Usage
fn main() {
println!("{}", largest_prime(13195));           // 29
println!("{}", largest_prime(600851475143));    // 6857
}

``````

Rust:

``````struct PrimesIterator {
found_primes: Vec<u64>,
next_to_check: u64,
}

impl PrimesIterator {
fn new() -> Self {
PrimesIterator {
found_primes: Vec::new(),
next_to_check: 2,
}
}
}

impl Iterator for PrimesIterator {
type Item = u64;
fn next(&mut self) -> Option<u64> {
for num in self.next_to_check.. {
if self.found_primes.iter().all(|prime| num % prime != 0) {
self.found_primes.push(num);
self.next_to_check = num + 1;
return Some(num);
}
}
unreachable!()
}
}

fn greatest_prime_divisor(mut number: u64) -> u64 {
for prime in PrimesIterator::new() {
while number % prime == 0 {
number /= prime;
}
if number <= 1 {
return prime;
}
}
unreachable!()
}

fn main() {
let number = std::env::args().nth(1).expect("Number must be first argument");
let number: u64 = number.parse().unwrap();
println!("The greatest prime divisor of {} is {}", number, greatest_prime_divisor(number));
}
``````

Result:

``````The greatest prime divisor of 600851475143 is 6857
``````

Scala:

``````def factors(n: Long, current: Int) = Stream.from(current)
.takeWhile(k => k * k <= n)
.find(n % _ == 0)

def largestPrimeFactor(n : Long, current : Int = 2): BigInt = {
factors(n, current) match {
case None => n
case Some(k) => largestPrimeFactor(n/k, k)
}
}

largestPrimeFactor(600851475143L)
``````

C :))

``````int main(void)
{
unsigned long long n = 600851475143ULL;
unsigned long long i;

for (i = 2ULL; i < n; i++) {
while (n % i == 0) {
n /= i;
}
}
printf("%llu\n", n);

return 0;
}
``````

PHP;

``````<?php
/**
* @Author: Erhan Kılıç
* @Website: http://erhankilic.org
* @Problem: The prime factors of 13195 are 5, 7, 13 and 29.
* What is the largest prime factor of the number 600851475143 ?
* https://projecteuler.net/problem=3
*/
class ProblemSolver
{
private \$original_number;
private \$number;
private \$current_prime_number = 2;
private \$prime_numbers = [];
private \$largest_prime_number;
/**
* ProblemSolver constructor.
* @param int \$number
*/
public function __construct(int \$number)
{
\$this->number = \$this->original_number = \$number;
}
/**
* Finds the next prime number
*/
private function find_next_prime_number()
{
if (\$this->current_prime_number == 2) {
\$this->current_prime_number++;
} else {
\$this->current_prime_number += 2;
}
\$can_divide = false;
\$number = 2;
while (\$number < \$this->current_prime_number) {
if (\$this->current_prime_number % \$number == 0) {
\$can_divide = true;
}
\$number++;
}
if (\$can_divide) {
\$this->find_next_prime_number();
}
}
/**
* Finds the prime factors and largest prime factor of given number
*/
public function find_prime_factors()
{
while (\$this->number > 0) {
if (\$this->number == 1) {
\$this->largest_prime_number = \$this->current_prime_number;
break;
} else {
if (\$this->number % \$this->current_prime_number == 0) {
\$this->prime_numbers[] = \$this->current_prime_number;
\$this->number /= \$this->current_prime_number;
} else {
\$this->find_next_prime_number();
}
}
}
echo \$this->largest_prime_number;
}
}
\$solver = new ProblemSolver(600851475143);
\$solver->find_prime_factors();
``````

Javascript;

``````'use strict';

/**
* @Author: Erhan Kılıç
* @Website: http://erhankilic.org
* @Problem: The prime factors of 13195 are 5, 7, 13 and 29.
* What is the largest prime factor of the number 600851475143 ?
* https://projecteuler.net/problem=3
*/

var number = 600851475143, prime_number = 2;

function find_next_prime_number() {
var can_divide = false;
var n = 2;
if (prime_number === 2) {
prime_number++;
} else {
prime_number += 2;
}
while (n < prime_number) {
if (prime_number % n === 0) {
can_divide = true;
}
n++;
}
if (can_divide) {
find_next_prime_number();
}
}

while (number > 1) {
if (number % prime_number === 0) {
number /= prime_number;
} else {
find_next_prime_number();
}
}
console.log(prime_number);
``````

Author: Brewyn
Largest Prime Factor

Javascript

```const isPrime = ( value ) => {
for( let i = 2; i < value; i++ )
if( value % i === 0 )
return false;
return true;
};

const LargestPrimeFactor = ( value ) => {
let result = [];
for( let i = 2; i < value; i++ )
if( isPrime( i ) )
if( value % i === 0 )
result.push( i );
return result;
};
console.log( LargestPrimeFactor( 600851475143 ) );
```

PHP

```
function isPrime( \$value ) {
for( \$i = 2; \$i < \$value; \$i++ )
if( \$value % \$i == 0 )
return false;
return true;
};

function LargestPrimeFactor ( \$value ) {
\$result = [];
for( \$i = 2; \$i < \$value; \$i++ )
if( isPrime( \$i ) )
if( \$value % \$i == 0 )
array_push( \$result, \$i );
return \$result;
};

print_r( LargestPrimeFactor( 13195 ) );
//Array(
//   => 5
//   => 7
//   => 13
//   => 29
//)
```

Python

```def isPrime( value ):
for i in range( 2, value ):
if value % i == 0:
return False
return True

def LargestPrimeFactor ( value ):
result = []
for i in range( 2, value ):
if isPrime( i ):
if value % i == 0:
result.append( i )
return result

print( LargestPrimeFactor( 600851475143 ) )
```

Java

```import java.util.Arrays;

class Main {
public static void main(String[] args) {

class LargestPrimeFactor {
public LargestPrimeFactor( int value ) {
System.out.println(Arrays.toString(this.LargestPrimeFactor(value)));
}

boolean isPrime(int value) {
for(int i = 2; i < value; i++) {
if(value % i == 0) {
return false;
}
}
return true;
}

int[] LargestPrimeFactor(int value) {
int result[] = new int;
int counter = 0;
for( int i = 2; i < value; i++ ) {
if( this.isPrime(i) ) {
if(value % i == 0){
result[counter] = i;
counter++;
}
}
}

return result;
}
}
LargestPrimeFactor myObject = new LargestPrimeFactor(600851475143);
// [ 5, 7, 13, 29 ]
}
}
```

Python!

``````def list_of_primes(n):
not_prime = set() # In is O(1) rather than O(N)
primes = set()
for i in xrange(2, n+1):
if i not in not_prime:
# Adds multiples of the number to the set of checked values
# i * (i-1) etc. are already updated so starts at i*i
not_prime.update(range(i*i, n+1, i))
return primes

def get_factors(n):
factors = set()
for i in xrange(1, int(n**0.5)):
if n % i == 0:
return list(factors)

def get_prime_factors(n):
factors = sorted(get_factors(n), reverse=True)
primes = list_of_primes(factors)
for factor in factors:
if factor in primes:
return factor
else:
return None

print(get_prime_factors(13195))
``````

Java

``````        Scanner in = new Scanner(System.in);
System.out.printf("Enter i Value:  ");
long n = in.nextLong();
long number = n;
long largestPrimeFactor = n;
long i = 2;
while (i <= n && n != 1) {
if (n % i == 0) {
n = n / i;
largestPrimeFactor = i;
}
else {
i = i+1;
}
}
System.out.println("The largest prime factor of the number "+ number + " is = "+ largestPrimeFactor);
``````
Classic DEV Post from Apr 30

## Who's looking for open source contributors? (April 30th edition)  