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!

Did you find this post useful? Show some love!
DISCUSSION (12)

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

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
Ben Halpern DEV.TO FOUNDER

Hey there, we see you aren't signed in. (Yes you, the reader. This is a fake comment.)

Please consider creating an account on dev.to. It literally takes a few seconds and we'd appreciate the support so much. ❤️

Plus, no fake comments when you're signed in. 🙃

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
}

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

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;
}
Classic DEV Post from Aug 8

Should tech companies use quotas to increase diversity?

Experts in diversity and inclusion share their thoughts on whether companies need to use quotas to increase diversity when hiring.

READ POST
Follow @lynnetye to see more of their posts in your feed.
Peter Kim Frank
Working on dev.to. Previously: on-demand tutoring and textbooks. Before that, ran/sold an online community and worked for the company that built Tinder. 😎
More from @peter
Assigned seats + missing ticket puzzle
#challenge
Project Euler #2 - Even Fibonacci numbers
#projecteuler #challenge
Trending on dev.to
Juggling Multiple Languages Simultaneously
#discuss
How long have you been programming?
#discuss
What Open-source Load Balancer Have You Used Before or Still Using Now?
#opensource #help #discuss
What is difference among enterprise architect, solution architect, software architect, system architect and cloud architect?
#discuss
Why Your Best Work is Hardest to Finish
#productivity #career #beginners
Who's looking for open source contributors? (September 17 edition)
#discuss #opensource
Thoughts on Dashboard Design
#data #dashboard #dataanalysis #productivity
What was your first PR on Github?
#github #discuss #programming