DEV Community

Project Euler #3 - Largest Prime Factor

Peter Kim Frank on June 20, 2018

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

Read full post

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

Ali Spittel • May 28 '19

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

Rossman • Aug 27 '22

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

        public Task3() 
        {
            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

Prabhjot Singh Rana • Feb 4 '20

Python:

maxnum = 600851475143  
result = 2

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

print(result)

JuriTuuti • Jun 20 '21 • Edited

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?

Seiei Miyagi • Jun 22 '18

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

Sagnik Ray • Jun 7 '20 • Edited

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