I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Largest prime factor

From Rosetta Code
Largest prime factor is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
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[edit]

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

AWK[edit]

 
# 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[edit]

FreeBASIC[edit]

#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[edit]

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

C[edit]

#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

F#[edit]

 
printfn "%d" (Seq.last<|Open.Numeric.Primes.Prime.Factors 600851475143L)
 
Output:
6857

Fermat[edit]

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[edit]

Translation of: Wren
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.

Julia[edit]

 using Primes
 
@show first(last(factor(600851475143).pe))
 
Output:
first(last((factor(600851475143)).pe)) = 6857

PARI/GP[edit]

A=factor(600851475143)
print(A[matsize(A)[1],1])
Output:
6857

Perl[edit]

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[edit]

with javascript_semantics
?prime_factors(600851475143,false,-1)[$]
Output:
6857

PL/I[edit]

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

Raku[edit]

Note: These are both extreme overkill for the task requirements.

Not particularly fast[edit]

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[edit]

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[edit]

 
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...

Wren[edit]

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[edit]

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