## DEV Community

Peter Kim Frank

Posted on • Updated on

# Project Euler #3 - Largest Prime Factor

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!

Seiei Miyagi

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
``````

Sunday Ezeilo

Nice one. But, I think y << prime, to_a.last pose addition execution time. Michael Kohl's approach is more optimized.

Khanh Tran • Edited

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;
}
``````

Sunday Ezeilo

C is a powerful language. The same algorithm in Ruby shows to have time complexity issue. Good code, bro!

khouloudzaiter

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);
``````

Erhan Kılıç

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(
//  [0] => 5
//  [1] => 7
//  [2] => 13
//  [3] => 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[4];
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 ]
}
}
```

Idan Arye • Edited

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
``````

Jay

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
}

``````

Patrick Waivers

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])
``````

Tobias Salzmann

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)
``````

Stephanie Handsteiner

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;
}
``````

rahy-hub

/*Largest prime factor

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

What is the largest prime factor of the number 600851475143 ?*/

# include

using namespace std;

int main()
{
long long num=600851475143 ,largest=1 ;
for(int i=2;i<=num;i++)
{
if(num%i==0)
{
num=num/i;
cout< if(i>largest)
largest=i;
}

}
cout<<"\n\n"<<"the largest prime factor of the number 600851475143 is "<<largest<<"\n";
return 0;
}

My code in C++ >>Output>>6857

Ali Spittel

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[0])
for factor in factors:
if factor in primes:
return factor
else:
return None

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

Rossman

C#

``````    internal class Task3
{
const long number = 600851475143;
long maxPrimeDivider = 2;
private static bool IsPrime(long number)
{
for (var divisor = 2; divisor <= Math.Sqrt(number); divisor++)
{
if (number % divisor == 0)
{
return false;
}
}
return true;
}

{
var numberSqrt = (long)Math.Sqrt(number);
Parallel.For(2, numberSqrt, num =>
{
if (number % num == 0 && IsPrime(num) && maxPrimeDivider < num)
{
maxPrimeDivider = num;
}
});
Console.WriteLine(maxPrimeDivider);
}
}
``````

Result

6857

Julia

function isprime(n)
a = ceil(Int,sqrt(n))+1
a=iseven(a) ? a+1 : a
for i = a:-2:3
if n % i == 0
return false
end
end
return true
end

function largest_prime(number)
sqrt_of_n = ceil(Int,sqrt(number)) # the answer must be less than square root of n
sqrt_of_n=iseven(sqrt_of_n) ? sqrt_of_n+1 : sqrt_of_n #a prime cannot be even, so only check odd numbers
for i = sqrt_of_n:-2:1

if number % i == 0 #if 600851475143 is divisible by i
if isprime(i) #then check if i is prime
return i
break
end
end
end
end

println(largest_prime(600851475143))

# How do I enter formatted code on this site?

Prabhjot Singh Rana

Python:

``````maxnum = 600851475143
result = 2

while maxnum > result:
if maxnum % result == 0:
maxnum = maxnum /result
else:
result = result +1

print(result)
``````

Seiei Miyagi

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