Problem 3 "Largest prime factor"

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

問 3 「最大の素因数」

13195 の素因数は 5, 7, 13, 29 である.

600851475143 の素因数のうち最大のものを求めよ.

fn divide_fully(n: &mut u64, d: u64, side: &mut u64) {
    if *n % d != 0 {
        return;
    }
    while {
        *n /= d;
        *n % d == 0
    } {}
    *side = (*n as f64).sqrt() as u64;
}

fn largest_prime_factor(mut n: u64) -> u64 {
    assert!(n > 1);
    let mut side = (n as f64).sqrt() as u64;
    let basic_primes = [2u64, 3, 5];
    for &d in &basic_primes {
        divide_fully(&mut n, d, &mut side);
        if n == 1 {
            return d;
        }
    }
    let mut divisor = 5u64;
    for i in [2u64, 4].iter().cycle() {
        divisor += *i;
        if divisor > side {
            break;
        }
        divide_fully(&mut n, divisor, &mut side);
        if n == 1 {
            return divisor;
        }
    }
    n
}

fn main() {
    let ans = largest_prime_factor(600851475143u64);
    assert_eq!(ans, 6857);
    println!("{}", ans);
    assert_eq!(largest_prime_factor(60), 5);
    assert_eq!(largest_prime_factor(5), 5);
    assert_eq!(largest_prime_factor(17), 17);
    assert_eq!(largest_prime_factor(6), 3);
    assert_eq!(largest_prime_factor(15), 5);
    assert_eq!(largest_prime_factor(25698751364526), 328513);
    assert_eq!(largest_prime_factor(13195), 29);
}

fn largest_prime_factor(mut n: u64) -> u64 {
    assert!(n > 1);
    let mut divisor = 2u64;
    while n != 1 {
        if n % divisor == 0 {
            n /= divisor;
        } else {
            divisor += 1;
        }
    }
    divisor
}

fn main() {
    let ans = largest_prime_factor(600851475143u64);
    assert_eq!(ans, 6857);
    println!("{}", ans);
    assert_eq!(largest_prime_factor(60), 5);
    assert_eq!(largest_prime_factor(5), 5);
    assert_eq!(largest_prime_factor(17), 17);
    assert_eq!(largest_prime_factor(6), 3);
    assert_eq!(largest_prime_factor(15), 5);
    assert_eq!(largest_prime_factor(25698751364526), 328513);
    assert_eq!(largest_prime_factor(13195), 29);
}

package main

import (
	"fmt"
	"log"
	"math"
)

func divideFully(n *uint64, d uint64, side *uint64) {
	if *n%d != 0 {
		return
	}
	for ok := true; ok; ok = *n%d == 0 {
		*n /= d
	}
	*side = uint64(math.Sqrt(float64(*n)))
}

type Divisor struct {
	d uint64
	f uint8
}

func (d *Divisor) increment() {
	d.d += uint64(2) << d.f
	d.f ^= 1
}

func largestPrimeFactor(n uint64) uint64 {
	if n < 2 {
		log.Fatal("n must be > 1.")
	}
	side := uint64(math.Sqrt(float64(n)))
	for _, d := range []uint64{2, 3, 5} {
		divideFully(&n, d, &side)
		if n == 1 {
			return d
		}
	}
	d := Divisor{d: 5}
	for {
		d.increment()
		if d.d > side {
			break
		}
		divideFully(&n, d.d, &side)
		if n == 1 {
			return d.d
		}
	}
	return n
}

func Example() {
	ans := largestPrimeFactor(600851475143)
	fmt.Println(ans)
	// Output: 6857
}
→ Go playground 
function assert(condition: any, msg?: string): asserts condition {
  if (!condition) {
    throw new Error(msg);
  }
}

class Divisor {
  d: number;
  #f: number;
  constructor() {
    this.d = 5;
    this.#f = 0;
  }
  increment() {
    this.d += 2 << this.#f;
    this.#f ^= 1;
  }
}

function divideFully(n: number, d: number, side: number): [number, number] {
  if (n % d != 0) {
    return [n, side];
  }
  do {
    n /= d | 0;
  } while (n % d === 0);
  return [n, Math.sqrt(n) | 0];
}

function largestPrimeFactor(n: number): number {
  assert(Number.isInteger(n));
  assert(n > 1);
  let side = Math.sqrt(n) | 0;
  for (const d of [2, 3, 5]) {
    [n, side] = divideFully(n, d, side);
    if (n === 1) {
      return d;
    }
  }
  const d = new Divisor();
  while (true) {
    d.increment();
    if (d.d > side) {
      break;
    }
    [n, side] = divideFully(n, d.d, side);
    if (n === 1) {
      return d.d;
    }
  }
  return n;
}

let ans = largestPrimeFactor(600851475143);
console.log(ans);
assert(ans === 6857);
→ TypeScript playground