Posted on Jun 20, 2018 • Edited on May 28, 2019

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!

Top comments (21)

Seiei Miyagi • Jun 20 '18

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 • May 11 '20

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

khouloudzaiter • Aug 5 '19

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

Khanh Tran • Jun 21 '18 • 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 • May 12 '20

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

Patrick Waivers • Jun 20 '18

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

Stephanie Handsteiner • Jun 21 '18

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

Tobias Salzmann • Jun 25 '18

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)

Jay • Jun 23 '18

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 }

Erhan Kılıç • Jun 21 '18

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

XBrewyn • Dec 30 '18 • Edited

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 • Jun 21 '18 • 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

rahy-hub • Apr 7 '20

/*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

View full discussion (21 comments)