loading...

Project Euler #3 - Largest Prime Factor

peter profile image Peter Kim Frank Updated on ・1 min read

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!

Discussion

pic
Editor guide
Collapse
hanachin profile image
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
Collapse
citizen428 profile image
Michael Kohl

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
Collapse
hanachin profile image
Seiei Miyagi

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

Thread Thread
citizen428 profile image
Michael Kohl

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

Collapse
ezeilosu profile image
Sunday Ezeilo

Well optimized code. You had to think a lot. Good one, bro!

Collapse
ezeilosu profile image
Sunday Ezeilo

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

Collapse
khanhtc1202 profile image
Khanh Tran

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;
}
Collapse
ezeilosu profile image
Sunday Ezeilo

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

Collapse
citizen428 profile image
Michael Kohl

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
Collapse
khouloudzaiter profile image
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);
Collapse
stephanie profile image
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;
}
Collapse
erhankilic profile image
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);
Collapse
xbrewyn profile image
XBrewyn

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 ]
  } 
}
Collapse
idanarye profile image
Idan Arye

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
Collapse
tobias_salzmann profile image
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)
Collapse
jay profile image
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
}

Collapse
pwaivers profile image
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])
Collapse
rahyhub profile image
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

Collapse
aspittel profile image
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:
            primes.add(i)
            # 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:
            factors.add(i)
            factors.add(n/i)
    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))
Collapse
prabh profile image
Prabhjot Singh Rana

Python:

maxnum = 600851475143  
result = 2

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

print(result)
Collapse
jacklangcreator profile image
Sagnik Ray

java is cool

static long IsPrime(long n){
int counter = 2;
long newval = n;
long larfact = 0;
while(counter*counter <= n){
if(newval % counter == 0){
newval = newval/counter;
larfact = counter;
}
else{
counter++;
}
}
if(newval > larfact){
larfact = newval;
}
return larfact;

but 600851475143 is coming under the range of the "long" data type of java but still it works for any value below it .
THE APPROACH IS PRETTY SIMPLE :
I used the the "Fundamental Theorem of Arithmetic" which states That Any Integer greater than 1 is either a prime number or product of prime numbers.
For example:
12
we start with smallest prime number 2.
the 12/2 = 6 which means that 2 is the prime factor 12.
If we try again by dividing the result by 2
6/2 = 3 . 3 is also a prime number . So the complete factorization is 2,2,3.

I have implemented this logic in the above code This works really fast .I think this code can be improved
a little bit Please some one suggest me.

Hope You like The implementation ;)

Collapse
asterpac profile image