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!

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 May 6

Vue vs React

Which one is better? Vue or React? Made a stupid site to track the stars of bo...

READ POST
Follow @ycmjason 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
Project Euler #2 - Even Fibonacci numbers
#projecteuler #challenge
Project Euler #1 - Multiples of 3 and 5
#projecteuler #challenge
Trending on dev.to
What's in your bookmarks bar?
#tools #productivity #discuss
On esoteric languages
#discuss #esoteric #code #fun
The Shell Introduction I Wish I Had
#shell #productivity #beginners #bash
What are your programming hype songs?
#discuss #music #productivity
Slack keeps interrupting you, but you can stop it
#programming #productivity
What has programming taught you that you keep-in-mind/use in your daily life?
#discuss
Spot the malware
#security #challenge #punycode
Lessons from releasing a personal project as a commercial product
#beginners #startup #showdev #career