Largest prime factor: Difference between revisions
(J) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 8: | Line 8: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
Based on the Wren and Go samples. |
Based on the Wren and Go samples. |
||
< |
<syntaxhighlight lang="algol68">BEGIN # find the largest prime factor of a number # |
||
# returns the largest prime factor of n # |
# returns the largest prime factor of n # |
||
PROC max prime factor = ( LONG INT n )LONG INT: |
PROC max prime factor = ( LONG INT n )LONG INT: |
||
Line 40: | Line 40: | ||
test( 6 008 ); |
test( 6 008 ); |
||
test( 751 ) |
test( 751 ) |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 49: | Line 49: | ||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
< |
<syntaxhighlight lang="autohotkey">MsgBox % result := max(prime_numbers(600851475143)*) |
||
prime_numbers(n) { |
prime_numbers(n) { |
||
Line 75: | Line 75: | ||
ans.push(Format("{:d}", n)) |
ans.push(Format("{:d}", n)) |
||
return ans |
return ans |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>6857</pre> |
<pre>6857</pre> |
||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f LARGEST_PRIME_FACTOR.AWK |
# syntax: GAWK -f LARGEST_PRIME_FACTOR.AWK |
||
# converted from FreeBASIC |
# converted from FreeBASIC |
||
Line 106: | Line 106: | ||
return(1) |
return(1) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 114: | Line 114: | ||
=={{header|BASIC}}== |
=={{header|BASIC}}== |
||
==={{header|FreeBASIC}}=== |
==={{header|FreeBASIC}}=== |
||
< |
<syntaxhighlight lang="freebasic">#include"isprime.bas" |
||
dim as ulongint n = 600851475143, j = 3 |
dim as ulongint n = 600851475143, j = 3 |
||
while not isprime(n) |
while not isprime(n) |
||
Line 120: | Line 120: | ||
j+=2 |
j+=2 |
||
wend |
wend |
||
print n</ |
print n</syntaxhighlight> |
||
{{out}}<pre>6857</pre> |
{{out}}<pre>6857</pre> |
||
==={{header|GW-BASIC}}=== |
==={{header|GW-BASIC}}=== |
||
No primality testing is even required. |
No primality testing is even required. |
||
< |
<syntaxhighlight lang="gwbasic">10 N#=600851475143# |
||
20 J#=3 |
20 J#=3 |
||
30 IF J#=N# THEN GOTO 100 |
30 IF J#=N# THEN GOTO 100 |
||
Line 131: | Line 131: | ||
50 J#=J#+2 |
50 J#=J#+2 |
||
60 GOTO 30 |
60 GOTO 30 |
||
100 PRINT N#</ |
100 PRINT N#</syntaxhighlight> |
||
{{output}}<pre>6857</pre> |
{{output}}<pre>6857</pre> |
||
=={{header|BCPL}}== |
=={{header|BCPL}}== |
||
This version creates a 2,3,5 wheel object, which is instantiated by the factorization routine. |
This version creates a 2,3,5 wheel object, which is instantiated by the factorization routine. |
||
<syntaxhighlight lang="bcpl"> |
|||
<lang BCPL> |
|||
GET "libhdr" |
GET "libhdr" |
||
Line 183: | Line 183: | ||
RESULTIS 0 |
RESULTIS 0 |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 191: | Line 191: | ||
</pre> |
</pre> |
||
=={{header|C}}== |
=={{header|C}}== |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
Line 213: | Line 213: | ||
printf( "%ld\n", n ); |
printf( "%ld\n", n ); |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}}<pre>6857</pre> |
{{out}}<pre>6857</pre> |
||
=={{header|CoffeeScript}}== |
=={{header|CoffeeScript}}== |
||
<syntaxhighlight lang="coffeescript"> |
|||
<lang CoffeeScript> |
|||
wheel235 = () -> |
wheel235 = () -> |
||
yield 2 |
yield 2 |
||
Line 241: | Line 241: | ||
console.log "The largest prime factor of 600,851,475,143 is #{gpf(600_851_475_143)}" |
console.log "The largest prime factor of 600,851,475,143 is #{gpf(600_851_475_143)}" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 247: | Line 247: | ||
</pre> |
</pre> |
||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
<syntaxhighlight lang="elixir"> |
|||
<lang Elixir> |
|||
defmodule Factor do |
defmodule Factor do |
||
def wheel235(), do: |
def wheel235(), do: |
||
Line 267: | Line 267: | ||
IO.puts "The largest prime factor of 600,851,475,143 is #{Factor.gpf(600_851_475_143)}" |
IO.puts "The largest prime factor of 600,851,475,143 is #{Factor.gpf(600_851_475_143)}" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 274: | Line 274: | ||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
Uses a factorization wheel, but without builtin lazy lists, it's rather awkward for a functional language. |
Uses a factorization wheel, but without builtin lazy lists, it's rather awkward for a functional language. |
||
<syntaxhighlight lang="erlang"> |
|||
<lang Erlang> |
|||
main(_) -> |
main(_) -> |
||
test(), |
test(), |
||
Line 291: | Line 291: | ||
101 = gpf(101), |
101 = gpf(101), |
||
23 = gpf(23 * 13). |
23 = gpf(23 * 13). |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 298: | Line 298: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
printfn "%d" (Seq.last<|Open.Numeric.Primes.Prime.Factors 600851475143L) |
printfn "%d" (Seq.last<|Open.Numeric.Primes.Prime.Factors 600851475143L) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 307: | Line 307: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
< |
<syntaxhighlight lang="factor">USING: math.primes.factors prettyprint sequences ; |
||
600851475143 factors last .</ |
600851475143 factors last .</syntaxhighlight> |
||
=={{header|Fermat}}== |
=={{header|Fermat}}== |
||
< |
<syntaxhighlight lang="fermat">n:=600851475143; |
||
j:=3; |
j:=3; |
||
while Isprime(n)<>1 do |
while Isprime(n)<>1 do |
||
Line 318: | Line 318: | ||
j:=j+2; |
j:=j+2; |
||
od; |
od; |
||
!!n;</ |
!!n;</syntaxhighlight> |
||
{{out}}<pre>6857</pre> |
{{out}}<pre>6857</pre> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{trans|Wren}} |
{{trans|Wren}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 365: | Line 365: | ||
n := uint64(600851475143) |
n := uint64(600851475143) |
||
fmt.Println("The largest prime factor of", n, "is", largestPrimeFactor(n), "\b.") |
fmt.Println("The largest prime factor of", n, "is", largestPrimeFactor(n), "\b.") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 373: | Line 373: | ||
=={{header|J}}== |
=={{header|J}}== |
||
{{trans|jq}}< |
{{trans|jq}}<syntaxhighlight lang="j"> {:q:600851475143 |
||
6857</ |
6857</syntaxhighlight> |
||
=={{header|jq}}== |
=={{header|jq}}== |
||
{{works with|jq}} |
{{works with|jq}} |
||
Line 380: | Line 380: | ||
Using `factors` as defined at [[Prime_decomposition#jq]]: |
Using `factors` as defined at [[Prime_decomposition#jq]]: |
||
<lang |
<syntaxhighlight lang="jq">600851475143 | last(factors)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 387: | Line 387: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia"> using Primes |
||
@show first(last(factor(600851475143).pe)) |
@show first(last(factor(600851475143).pe)) |
||
</ |
</syntaxhighlight>{{out}}<pre>first(last((factor(600851475143)).pe)) = 6857</pre> |
||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">Max[FactorInteger[600851475143][[All, 1]]]</syntaxhighlight> |
||
{{out}}<pre> |
{{out}}<pre> |
||
Line 399: | Line 399: | ||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
< |
<syntaxhighlight lang="parigp">A=factor(600851475143) |
||
print(A[matsize(A)[1],1])</ |
print(A[matsize(A)[1],1])</syntaxhighlight> |
||
{{out}}<pre>6857</pre> |
{{out}}<pre>6857</pre> |
||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
use feature 'say'; |
use feature 'say'; |
||
Line 413: | Line 413: | ||
} |
} |
||
say +(f 600851475143)[-2]</ |
say +(f 600851475143)[-2]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>6857</pre> |
<pre>6857</pre> |
||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">prime_factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">600851475143</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)[$]</span> |
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">prime_factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">600851475143</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)[$]</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 429: | Line 429: | ||
=={{header|PL/I}}== |
=={{header|PL/I}}== |
||
Based on the Wren, Go and Algol 68 samples. |
Based on the Wren, Go and Algol 68 samples. |
||
< |
<syntaxhighlight lang="pli">/* find the largest prime factor of 600851475143 */ |
||
largestPrimeFactor: procedure options( main ); |
largestPrimeFactor: procedure options( main ); |
||
declare ( n, maxFactor, v, k, rootN ) decimal( 12 )fixed; |
declare ( n, maxFactor, v, k, rootN ) decimal( 12 )fixed; |
||
Line 452: | Line 452: | ||
if v > 1 then maxFactor = v; |
if v > 1 then maxFactor = v; |
||
put skip list( 'Largest prime factor of ', n, ' is ', maxFactor ); |
put skip list( 'Largest prime factor of ', n, ' is ', maxFactor ); |
||
end largestPrimeFactor;</ |
end largestPrimeFactor;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 459: | Line 459: | ||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
<syntaxhighlight lang="prolog"> |
|||
<lang Prolog> |
|||
wheel2357(L) :- |
wheel2357(L) :- |
||
W = [2, 4, 2, 4, 6, 2, 6, 4, |
W = [2, 4, 2, 4, 6, 2, 6, 4, |
||
Line 488: | Line 488: | ||
?- main. |
?- main. |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 496: | Line 496: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang="python">#!/usr/bin/python |
||
def isPrime(n): |
def isPrime(n): |
||
Line 511: | Line 511: | ||
n /= j |
n /= j |
||
j += 2 |
j += 2 |
||
print(n);</ |
print(n);</syntaxhighlight> |
||
=={{header|R}}== |
=={{header|R}}== |
||
First uses the Sieve of Eratosthenes to find possible factors then tests each possible prime p for divisibility and also n/p. |
First uses the Sieve of Eratosthenes to find possible factors then tests each possible prime p for divisibility and also n/p. |
||
<syntaxhighlight lang="r"> |
|||
<lang R> |
|||
sieve <- function(n) { |
sieve <- function(n) { |
||
if (n < 2) |
if (n < 2) |
||
Line 547: | Line 547: | ||
cat("The prime factors of 600,851,475,143 are", paste(prime.factors(600851475143), collapse = ", "), "\n") |
cat("The prime factors of 600,851,475,143 are", paste(prime.factors(600851475143), collapse = ", "), "\n") |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 558: | Line 558: | ||
===Not particularly fast=== |
===Not particularly fast=== |
||
Pure Raku. Using [https://modules.raku.org/search/?q=Prime%3A%3AFactor Prime::Factor] from the [https://modules.raku.org/ Raku ecosystem]. Makes it to 2^95 - 1 in 1 second on my system. |
Pure Raku. Using [https://modules.raku.org/search/?q=Prime%3A%3AFactor Prime::Factor] from the [https://modules.raku.org/ Raku ecosystem]. Makes it to 2^95 - 1 in 1 second on my system. |
||
<lang |
<syntaxhighlight lang="raku" line>use Prime::Factor; |
||
my $start = now; |
my $start = now; |
||
Line 565: | Line 565: | ||
say "Largest prime factor of $_: ", max prime-factors $_; |
say "Largest prime factor of $_: ", max prime-factors $_; |
||
last if now - $start > 1; # quit after one second of total run time |
last if now - $start > 1; # quit after one second of total run time |
||
}</ |
}</syntaxhighlight> |
||
<pre>Largest prime factor of 600851475143: 6857 |
<pre>Largest prime factor of 600851475143: 6857 |
||
Line 666: | Line 666: | ||
Using [[:Category:Perl|Perl 5]] [[:Category:ntheory|ntheory]] library via [https://modules.raku.org/search/?q=Inline%3A%3APerl5 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).'' |
Using [[:Category:Perl|Perl 5]] [[:Category:ntheory|ntheory]] library via [https://modules.raku.org/search/?q=Inline%3A%3APerl5 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 |
<syntaxhighlight lang="raku" line>use Inline::Perl5; |
||
my $p5 = Inline::Perl5.new(); |
my $p5 = Inline::Perl5.new(); |
||
$p5.use: 'ntheory'; |
$p5.use: 'ntheory'; |
||
Line 676: | Line 676: | ||
say "Largest prime factor of $_: ", lpf "$_"; |
say "Largest prime factor of $_: ", lpf "$_"; |
||
last if now - $start > 1; # quit after one second of total run time |
last if now - $start > 1; # quit after one second of total run time |
||
}</ |
}</syntaxhighlight> |
||
Same output only much longer. |
Same output only much longer. |
||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
load "stdlib.ring" |
load "stdlib.ring" |
||
see "working..." + nl |
see "working..." + nl |
||
Line 699: | Line 699: | ||
see "" + n + nl |
see "" + n + nl |
||
see "done..." + nl |
see "done..." + nl |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 709: | Line 709: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">var n = 600851475143 |
||
say gpf(n) #=> 6857 |
say gpf(n) #=> 6857 |
||
say factor(n).last #=> 6857</ |
say factor(n).last #=> 6857</syntaxhighlight> |
||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
Without using any library functions at all (it's a one-liner otherwise): |
Without using any library functions at all (it's a one-liner otherwise): |
||
< |
<syntaxhighlight lang="ecmascript">var largestPrimeFactor = Fn.new { |n| |
||
if (!n.isInteger || n < 2) return 1 |
if (!n.isInteger || n < 2) return 1 |
||
var inc = [4, 2, 4, 2, 4, 6, 2, 6] |
var inc = [4, 2, 4, 2, 4, 6, 2, 6] |
||
Line 747: | Line 747: | ||
var n = 600851475143 |
var n = 600851475143 |
||
System.print("The largest prime factor of %(n) is %(largestPrimeFactor.call(n)).")</ |
System.print("The largest prime factor of %(n) is %(largestPrimeFactor.call(n)).")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 755: | Line 755: | ||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
< |
<syntaxhighlight lang="xpl0">real Num, Max, Div, Quot; |
||
[Num:= 600851475143.; |
[Num:= 600851475143.; |
||
Max:= 0.; |
Max:= 0.; |
||
Line 771: | Line 771: | ||
Format(1, 0); |
Format(1, 0); |
||
RlOut(0, Max); |
RlOut(0, Max); |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
Revision as of 17:32, 27 August 2022
- 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.
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
- Output:
Largest prime factor of 600851475143 is 6857 Largest prime factor of 6008 is 751 Largest prime factor of 751 is 751
AutoHotkey
MsgBox % result := max(prime_numbers(600851475143)*)
prime_numbers(n) {
if (n <= 3)
return [n]
ans := [], done := false
while !done {
if !Mod(n,2)
ans.push(2), n /= 2
else if !Mod(n,3)
ans.push(3), n /= 3
else if (n = 1)
return ans
else {
sr := sqrt(n), done := true, i := 6
while (i <= sr+6) {
if !Mod(n, i-1) ; is n divisible by i-1?
ans.push(i-1), n /= i-1, done := false
if !Mod(n, i+1) ; is n divisible by i+1?
ans.push(i+1), n /= i+1, done := false
if !done
break
i+=6
}}}
ans.push(Format("{:d}", n))
return ans
}
- Output:
6857
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)
}
- Output:
The largest prime factor of 600851475143 is 6857
BASIC
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
- Output:
6857
GW-BASIC
No primality testing is even required.
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#
- Output:
6857
BCPL
This version creates a 2,3,5 wheel object, which is instantiated by the factorization routine.
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
}
- 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
#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;
}
- Output:
6857
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)}"
- Output:
The largest prime factor of 600,851,475,143 is 6857
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)}"
- 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.
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).
- Output:
The largest prime factor of 600,851,475,143 is 6857
F#
printfn "%d" (Seq.last<|Open.Numeric.Primes.Prime.Factors 600851475143L)
- Output:
6857
Factor
USING: math.primes.factors prettyprint sequences ;
600851475143 factors last .
Fermat
n:=600851475143;
j:=3;
while Isprime(n)<>1 do
if Divides(j, n) then n:=n/j fi;
j:=j+2;
od;
!!n;
- Output:
6857
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.")
}
- Output:
The largest prime factor of 600851475143 is 6857.
J
{:q:600851475143
6857
jq
Works with gojq, the Go implementation of jq
Using `factors` as defined at Prime_decomposition#jq:
600851475143 | last(factors)
- Output:
6857
Julia
using Primes
@show first(last(factor(600851475143).pe))
- Output:
first(last((factor(600851475143)).pe)) = 6857
Mathematica / Wolfram Language
Max[FactorInteger[600851475143][[All, 1]]]
- Output:
6857
PARI/GP
A=factor(600851475143)
print(A[matsize(A)[1],1])
- Output:
6857
Perl
use strict;
use warnings;
use feature 'say';
sub f {
my($n) = @_;
$n % $_ or return $_, f($n/$_) for 2..$n
}
say +(f 600851475143)[-2]
- Output:
6857
Phix
with javascript_semantics ?prime_factors(600851475143,false,-1)[$]
- Output:
6857
PL/I
Based on the Wren, Go and Algol 68 samples.
/* 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;
- Output:
Largest prime factor of 600851475143 is 6857
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.
- Output:
The largest prime factor of 600,851,475,143 is 6857
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);
R
First uses the Sieve of Eratosthenes to find possible factors then tests each possible prime p for divisibility and also n/p.
sieve <- function(n) {
if (n < 2)
return (NULL)
primes <- rep(TRUE, n)
primes[1] <- FALSE
for (i in 1:floor(sqrt(n)))
if (primes[i])
primes[seq(i*i, n, by = i)] <- FALSE
which(primes)
}
prime.factors <- function(n) {
primes <- sieve(floor(sqrt(n)))
factors <- primes[n %% primes == 0]
if (length(factors) == 0)
n
else {
for (p in factors) { # add all elements of n/p that are also prime
d <- n / p
if (d != p && all(d %% primes[primes <= floor(sqrt(d))] != 0))
factors <- c(factors, d)
}
factors
}
}
cat("The prime factors of 600,851,475,143 are", paste(prime.factors(600851475143), collapse = ", "), "\n")
- Output:
The prime factors of 600,851,475,143 are 71, 839, 1471, 6857
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.
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
}
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).
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
}
Same output only much longer.
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
- Output:
working... The largest prime factor of the number 600851475143 is: 6857 done...
Sidef
var n = 600851475143
say gpf(n) #=> 6857
say factor(n).last #=> 6857
Wren
Without using any library functions at all (it's a one-liner otherwise):
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)).")
- Output:
The largest prime factor of 600851475143 is 6857.
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);
]
- Output:
6857