Largest prime factor
- Task
The task description is taken for Project Euler (https://projecteuler.net/problem=3)
What is the largest prime factor of the number 600851475143 ?
ALGOL 68
Based on the Wren and Go samples. <lang algol68>BEGIN # find the largest prime factor of a number #
# returns the largest prime factor of n # PROC max prime factor = ( LONG INT n )LONG INT: IF n < 2 THEN 1 ELSE LONG INT max factor := n; # even factors - only 2 is prime # LONG INT v := n; WHILE NOT ODD v DO max factor := 2; v OVERAB 2 OD; # odd factors # LONG INT k := 3; LONG INT root n = ENTIER long sqrt( n ); WHILE k <= root n AND v > 1 DO WHILE v MOD k = 0 AND v > 1 DO max factor := k; v OVERAB k OD; k +:= 2 OD; IF v > 1 THEN v ELSE max factor FI FI # max prime factor # ; # test the max prime factor routine # PROC test = ( LONG INT n )VOID: print( ( "Largest prime factor of ", whole( n, 0 ), " is ", whole( max prime factor( n ), 0 ), newline ) ); # test cases # test( 600 851 475 143 ); test( 6 008 ); test( 751 )
END</lang>
- Output:
Largest prime factor of 600851475143 is 6857 Largest prime factor of 6008 is 751 Largest prime factor of 751 is 751
AWK
<lang AWK>
- syntax: GAWK -f LARGEST_PRIME_FACTOR.AWK
- converted from FreeBASIC
BEGIN {
N = n = "600851475143" j = 3 while (!is_prime(n)) { if (n % j == 0) { n /= j } j += 2 } printf("The largest prime factor of %s is %d\n",N,n) exit(0)
} function is_prime(x, i) {
if (x <= 1) { return(0) } for (i=2; i<=int(sqrt(x)); i++) { if (x % i == 0) { return(0) } } return(1)
} </lang>
- Output:
The largest prime factor of 600851475143 is 6857
BASIC
FreeBASIC
<lang freebasic>#include"isprime.bas" dim as ulongint n = 600851475143, j = 3 while not isprime(n)
if n mod j = 0 then n/=j j+=2
wend print n</lang>
- Output:
6857
GW-BASIC
No primality testing is even required. <lang gwbasic>10 N#=600851475143# 20 J#=3 30 IF J#=N# THEN GOTO 100 40 IF INT(N#/J#) = N#/J# THEN N# = N#/J# 50 J#=J#+2 60 GOTO 30 100 PRINT N#</lang>
- Output:
6857
BCPL
This version creates a 2,3,5 wheel object, which is instantiated by the factorization routine. <lang BCPL> GET "libhdr"
LET new_235wheel() = VALOF {
LET w = getvec(1) w!0 := 1 // accumulator w!1 := -3 // index (negative => first few primes) RESULTIS w
}
LET next235(w) = VALOF {
LET p3 = TABLE 2, 3, 5 LET wheel235 = TABLE 6, 4, 2, 4, 2, 4, 6, 2 LET a, i = w!0, w!1
TEST i < 0 THEN { a := p3[i + 3] i +:= 1 } ELSE { a +:= wheel235[i] i := (i + 1) & 7 w!0 := a } w!1 := i RESULTIS a
}
LET gpf(n) = VALOF {
LET w = new_235wheel() LET d = next235(w)
UNTIL d*d > n { TEST n MOD d = 0 THEN n /:= d ELSE d := next235(w) }
freevec(w) RESULTIS n
}
LET start() = VALOF {
writef("The largest prime factor of 600,851,475,143 is %d *n", gpf(600_851_475_143)) RESULTIS 0
} </lang>
- Output:
BCPL 64-bit Cintcode System (13 Jan 2020) 0.000> The largest prime factor of 600,851,475,143 is 6857 0.001>
C
<lang c>#include <stdio.h>
- include <stdlib.h>
int isprime( long int n ) {
int i=3; if(!(n%2)) return 0; while( i*i < n ) { if(!(n%i)) return 0; i+=2; } return 1;
}
int main(void) {
long int n=600851475143, j=3;
while(!isprime(n)) { if(!(n%j)) n/=j; j+=2; } printf( "%ld\n", n ); return 0;
}</lang>
- Output:
6857
CoffeeScript
<lang CoffeeScript> wheel235 = () ->
yield 2 yield 3 yield 5 a = 1 i = 0 wheel = [6, 4, 2, 4, 2, 4, 6, 2] loop a += wheel[i] yield a i = (i + 1) & 7
gpf = (n) ->
w = wheel235() d = w.next().value until d*d > n if n % d is 0 n //= d else d = w.next().value n
console.log "The largest prime factor of 600,851,475,143 is #{gpf(600_851_475_143)}" </lang>
- Output:
The largest prime factor of 600,851,475,143 is 6857
Elixir
<lang Elixir> defmodule Factor do
def wheel235(), do: Stream.concat( [2, 3, 5], Stream.scan(Stream.cycle([6, 4, 2, 4, 2, 4, 6, 2]), 1, &+/2) )
def gpf(n), do: gpf n, wheel235() defp gpf(n, divs) do [d] = Enum.take divs, 1 cond do d*d > n -> n rem(n, d) === 0 -> gpf div(n, d), divs true -> gpf n, Stream.drop(divs, 1) end end
end
IO.puts "The largest prime factor of 600,851,475,143 is #{Factor.gpf(600_851_475_143)}" </lang>
- Output:
The largest prime factor of 600,851,475,143 is 6857
Erlang
Uses a factorization wheel, but without builtin lazy lists, it's rather awkward for a functional language. <lang Erlang> main(_) ->
test(), io:format("The largest prime factor of 600,851,475,143 is ~w~n", [gpf(600851475143)]).
gpf(N) -> gpf(N, 2, 0, <<1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6>>). gpf(N, D, J, Wheel) when J =:= byte_size(Wheel) -> gpf(N, D, 3, Wheel); gpf(N, D, _, _) when D*D > N -> N; gpf(N, D, J, Wheel) when N rem D =:= 0 -> gpf(N div D, D, J, Wheel); gpf(N, D, J, Wheel) -> gpf(N, D + binary:at(Wheel, J), J + 1, Wheel).
test() ->
3 = gpf(27), 5 = gpf(125), 7 = gpf(98), 101 = gpf(101), 23 = gpf(23 * 13).
</lang>
- Output:
The largest prime factor of 600,851,475,143 is 6857
F#
<lang fsharp> printfn "%d" (Seq.last<|Open.Numeric.Primes.Prime.Factors 600851475143L) </lang>
- Output:
6857
Fermat
<lang fermat>n:=600851475143; j:=3; while Isprime(n)<>1 do
if Divides(j, n) then n:=n/j fi; j:=j+2;
od; !!n;</lang>
- Output:
6857
Go
<lang go>package main
import "fmt"
func largestPrimeFactor(n uint64) uint64 {
if n < 2 { return 1 } inc := [8]uint64{4, 2, 4, 2, 4, 6, 2, 6} max := uint64(1) for n%2 == 0 { max = 2 n /= 2 } for n%3 == 0 { max = 3 n /= 3 } for n%5 == 0 { max = 5 n /= 5 } k := uint64(7) i := 0 for k*k <= n { if n%k == 0 { max = k n /= k } else { k += inc[i] i = (i + 1) % 8 } } if n > 1 { return n } return max
}
func main() {
n := uint64(600851475143) fmt.Println("The largest prime factor of", n, "is", largestPrimeFactor(n), "\b.")
}</lang>
- Output:
The largest prime factor of 600851475143 is 6857.
jq
Works with gojq, the Go implementation of jq
Using `factors` as defined at Prime_decomposition#jq: <lang jq>600851475143 | last(factors)</lang>
- Output:
6857
Julia
<lang julia> using Primes
@show first(last(factor(600851475143).pe))
</lang>
- Output:
first(last((factor(600851475143)).pe)) = 6857
Mathematica / Wolfram Language
<lang Mathematica>Max[FactorInteger[600851475143]All, 1]</lang>
- Output:
6857
PARI/GP
<lang parigp>A=factor(600851475143) print(A[matsize(A)[1],1])</lang>
- Output:
6857
Perl
<lang perl>use strict; use warnings; use feature 'say';
sub f {
my($n) = @_; $n % $_ or return $_, f($n/$_) for 2..$n
}
say +(f 600851475143)[-2]</lang>
- Output:
6857
Phix
with javascript_semantics ?prime_factors(600851475143,false,-1)[$]
- Output:
6857
PL/I
Based on the Wren, Go and Algol 68 samples. <lang pli>/* find the largest prime factor of 600851475143 */ largestPrimeFactor: procedure options( main );
declare ( n, maxFactor, v, k, rootN ) decimal( 12 )fixed; n = 600851475143; maxFactor = n; /* even factors */ v = n; do while( mod( v, 2 ) = 0 ); maxFactor = 2; v = v / 2; end; /* odd factors */ k = 3; rootN = sqrt( n ); do while( k <= rootN & v > 1 ); do while( mod( v, k ) = 0 & v > 1 ); maxFactor = k; v = v / k; end; k = k + 2; end; if v > 1 then maxFactor = v; put skip list( 'Largest prime factor of ', n, ' is ', maxFactor );
end largestPrimeFactor;</lang>
- Output:
Largest prime factor of 600851475143 is 6857
Prolog
<lang Prolog> wheel2357(L) :-
W = [2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10 | W], L = [1, 2, 2, 4 | W].
gpf(N, P) :- % greatest prime factor
wheel2357(W), gpf(N, 2, W, P).
gpf(N, D, _, N) :- D*D > N, !. gpf(N, D, W, X) :-
N mod D =:= 0, !, N2 is N/D, gpf(N2, D, W, X).
gpf(N, D, [S|Ss], X) :-
plus(D, S, D2), gpf(N, D2, Ss, X).
main :-
gpf(600_851_475_143, Euler003), format("The largest prime factor of 600,851,475,143 is ~p~n", [Euler003]), halt.
?- main. </lang>
- Output:
The largest prime factor of 600,851,475,143 is 6857
Python
<lang python>#!/usr/bin/python
def isPrime(n):
for i in range(2, int(n**0.5) + 1): if n % i == 0: return False return True
if __name__ == '__main__':
n = 600851475143 j = 3 while not isPrime(n): if n % j == 0: n /= j j += 2 print(n);</lang>
Raku
Note: These are both extreme overkill for the task requirements.
Not particularly fast
Pure Raku. Using Prime::Factor from the Raku ecosystem. Makes it to 2^95 - 1 in 1 second on my system. <lang perl6>use Prime::Factor;
my $start = now;
for flat 600851475143, (1..∞).map: { 2 +< $_ - 1 } {
say "Largest prime factor of $_: ", max prime-factors $_; last if now - $start > 1; # quit after one second of total run time
}</lang>
Largest prime factor of 600851475143: 6857 Largest prime factor of 3: 3 Largest prime factor of 7: 7 Largest prime factor of 15: 5 Largest prime factor of 31: 31 Largest prime factor of 63: 7 Largest prime factor of 127: 127 Largest prime factor of 255: 17 Largest prime factor of 511: 73 Largest prime factor of 1023: 31 Largest prime factor of 2047: 89 Largest prime factor of 4095: 13 Largest prime factor of 8191: 8191 Largest prime factor of 16383: 127 Largest prime factor of 32767: 151 Largest prime factor of 65535: 257 Largest prime factor of 131071: 131071 Largest prime factor of 262143: 73 Largest prime factor of 524287: 524287 Largest prime factor of 1048575: 41 Largest prime factor of 2097151: 337 Largest prime factor of 4194303: 683 Largest prime factor of 8388607: 178481 Largest prime factor of 16777215: 241 Largest prime factor of 33554431: 1801 Largest prime factor of 67108863: 8191 Largest prime factor of 134217727: 262657 Largest prime factor of 268435455: 127 Largest prime factor of 536870911: 2089 Largest prime factor of 1073741823: 331 Largest prime factor of 2147483647: 2147483647 Largest prime factor of 4294967295: 65537 Largest prime factor of 8589934591: 599479 Largest prime factor of 17179869183: 131071 Largest prime factor of 34359738367: 122921 Largest prime factor of 68719476735: 109 Largest prime factor of 137438953471: 616318177 Largest prime factor of 274877906943: 524287 Largest prime factor of 549755813887: 121369 Largest prime factor of 1099511627775: 61681 Largest prime factor of 2199023255551: 164511353 Largest prime factor of 4398046511103: 5419 Largest prime factor of 8796093022207: 2099863 Largest prime factor of 17592186044415: 2113 Largest prime factor of 35184372088831: 23311 Largest prime factor of 70368744177663: 2796203 Largest prime factor of 140737488355327: 13264529 Largest prime factor of 281474976710655: 673 Largest prime factor of 562949953421311: 4432676798593 Largest prime factor of 1125899906842623: 4051 Largest prime factor of 2251799813685247: 131071 Largest prime factor of 4503599627370495: 8191 Largest prime factor of 9007199254740991: 20394401 Largest prime factor of 18014398509481983: 262657 Largest prime factor of 36028797018963967: 201961 Largest prime factor of 72057594037927935: 15790321 Largest prime factor of 144115188075855871: 1212847 Largest prime factor of 288230376151711743: 3033169 Largest prime factor of 576460752303423487: 3203431780337 Largest prime factor of 1152921504606846975: 1321 Largest prime factor of 2305843009213693951: 2305843009213693951 Largest prime factor of 4611686018427387903: 2147483647 Largest prime factor of 9223372036854775807: 649657 Largest prime factor of 18446744073709551615: 6700417 Largest prime factor of 36893488147419103231: 145295143558111 Largest prime factor of 73786976294838206463: 599479 Largest prime factor of 147573952589676412927: 761838257287 Largest prime factor of 295147905179352825855: 131071 Largest prime factor of 590295810358705651711: 10052678938039 Largest prime factor of 1180591620717411303423: 122921 Largest prime factor of 2361183241434822606847: 212885833 Largest prime factor of 4722366482869645213695: 38737 Largest prime factor of 9444732965739290427391: 9361973132609 Largest prime factor of 18889465931478580854783: 616318177 Largest prime factor of 37778931862957161709567: 10567201 Largest prime factor of 75557863725914323419135: 525313 Largest prime factor of 151115727451828646838271: 581283643249112959 Largest prime factor of 302231454903657293676543: 22366891 Largest prime factor of 604462909807314587353087: 1113491139767 Largest prime factor of 1208925819614629174706175: 4278255361 Largest prime factor of 2417851639229258349412351: 97685839 Largest prime factor of 4835703278458516698824703: 8831418697 Largest prime factor of 9671406556917033397649407: 57912614113275649087721 Largest prime factor of 19342813113834066795298815: 14449 Largest prime factor of 38685626227668133590597631: 9520972806333758431 Largest prime factor of 77371252455336267181195263: 2932031007403 Largest prime factor of 154742504910672534362390527: 9857737155463 Largest prime factor of 309485009821345068724781055: 2931542417 Largest prime factor of 618970019642690137449562111: 618970019642690137449562111 Largest prime factor of 1237940039285380274899124223: 18837001 Largest prime factor of 2475880078570760549798248447: 23140471537 Largest prime factor of 4951760157141521099596496895: 2796203 Largest prime factor of 9903520314283042199192993791: 658812288653553079 Largest prime factor of 19807040628566084398385987583: 165768537521 Largest prime factor of 39614081257132168796771975167: 30327152671
Particularly fast
Using Perl 5 ntheory library via Inline::Perl5. Makes it to about 2^155 - 1 in 1 second on my system. Varies from 2^145-1 (lowest seen) to 2^168-1 (highest seen).
<lang perl6>use Inline::Perl5; my $p5 = Inline::Perl5.new(); $p5.use: 'ntheory'; my &lpf = $p5.run('sub { ntheory::todigitstring ntheory::vecmax ntheory::factor $_[0] }');
my $start = now;
for flat 600851475143, (1..∞).map: { 2 +< $_ - 1 } {
say "Largest prime factor of $_: ", lpf "$_"; last if now - $start > 1; # quit after one second of total run time
}</lang> Same output only much longer.
Ring
<lang ring> load "stdlib.ring" see "working..." + nl see "The largest prime factor of the number 600851475143 is:" + nl num = 600851475143 numSqrt = sqrt(num) numSqrt = floor(numSqrt) if numSqrt%2 = 0
numSqrt++
ok
for n = numSqrt to 3 step -2
if isprime(n) and num%n = 0 exit ok
next
see "" + n + nl see "done..." + nl </lang>
- Output:
working... The largest prime factor of the number 600851475143 is: 6857 done...
Sidef
<lang ruby>var n = 600851475143
say gpf(n) #=> 6857 say factor(n).last #=> 6857</lang>
Wren
Without using any library functions at all (it's a one-liner otherwise): <lang ecmascript>var largestPrimeFactor = Fn.new { |n|
if (!n.isInteger || n < 2) return 1 var inc = [4, 2, 4, 2, 4, 6, 2, 6] var max = 1 while (n%2 == 0) { max = 2 n = (n/2).floor } while (n%3 == 0) { max = 3 n = (n/3).floor } while (n%5 == 0) { max = 5 n = (n/5).floor } var k = 7 var i = 0 while (k * k <= n) { if (n%k == 0) { max = k n = (n/k).floor } else { k = k + inc[i] i = (i + 1) % 8 } } return (n > 1) ? n : max
}
var n = 600851475143 System.print("The largest prime factor of %(n) is %(largestPrimeFactor.call(n)).")</lang>
- Output:
The largest prime factor of 600851475143 is 6857.
XPL0
<lang XPL0>real Num, Max, Div, Quot; [Num:= 600851475143.; Max:= 0.; Div:= 2.; repeat loop [Quot:= Num / Div;
if Mod(Quot, 1.) < 1E-10 then \evenly divisible [Num:= Quot; Max:= Div; ] else quit; if Div > Num then quit; ]; Div:= Div + 1.;
until Div > Num; Format(1, 0); RlOut(0, Max); ]</lang>
- Output:
6857