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

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.

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

## AWK

` # syntax: GAWK -f LARGEST_PRIME_FACTOR.AWK# converted from FreeBASICBEGIN {    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 = 3while not isprime(n)    if n mod j = 0 then n/=j    j+=2wendprint n`
Output:
`6857`

### GW-BASIC

No primality testing is even required.

`10 N#=600851475143#20 J#=330 IF J#=N# THEN GOTO 10040 IF INT(N#/J#) = N#/J# THEN N# = N#/J#50 J#=J#+260 GOTO 30100 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   endend 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

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

## jq

Works with: 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..." + nlsee "The largest prime factor of the number 600851475143 is:" + nlnum = 600851475143numSqrt = 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    oknext see "" + n + nlsee "done..." + nl `
Output:
```working...
The largest prime factor of the number 600851475143 is:
6857
done...
```

## Sidef

`var n = 600851475143 say gpf(n)             #=> 6857say 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 = 600851475143System.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
```