Rosetta Code

Largest prime factor: Difference between revisions

Page Discussion

Largest prime factor (view source)

Revision as of 18:03, 21 April 2024

14,487 bytes added ,  28 days ago
Added Easylang
m (→‎{{header|Perl}}: stray char)
(Added Easylang)
 
(32 intermediate revisions by 20 users not shown)
Line 5:
<br>What is the largest prime factor of the number 600851475143 ?
<br><br>
 
=={{header|11l}}==
{{trans|Python}}
 
<syntaxhighlight lang="11l">
F isPrime(n)
L(i) 2 .. Int(n ^ 0.5)
I n % i == 0
R 0B
R 1B
 
V n = 600851475143
V j = 3
L !isPrime(n)
I n % j == 0
n I/= j
j += 2
print(n)
</syntaxhighlight>
 
{{out}}
<pre>
6857
</pre>
 
=={{header|ALGOL 68}}==
Based on the Wren and Go samples.
<langsyntaxhighlight 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:
Line 40 ⟶ 64:
test( 6 008 );
test( 751 )
END</langsyntaxhighlight>
{{out}}
<pre>
Line 46 ⟶ 70:
Largest prime factor of 6008 is 751
Largest prime factor of 751 is 751
</pre>
 
=={{header|Arturo}}==
 
<syntaxhighlight lang="arturo">print max factors.prime 600851475143</syntaxhighlight>
 
{{out}}
 
<pre>6857</pre>
 
=={{header|AutoHotkey}}==
<syntaxhighlight lang="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
}</syntaxhighlight>
{{out}}
<pre>6857</pre>
 
=={{header|AWK}}==
<syntaxhighlight 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)
}
</syntaxhighlight>
{{out}}
<pre>
The largest prime factor of 600851475143 is 6857
</pre>
 
=={{header|BASIC}}==
==={{header|Applesoft BASIC}}===
Código sacado de https://www.calormen.com/jsbasic/ El código original es de Christiano Trabuio.
<syntaxhighlight lang="qbasic">100 HOME
110 LET a = 600851475143
120 LET f = 0
130 IF a/2 = INT(a/2) THEN LET a = a/2: LET f = 1: GOTO 130
140 LET i = 3
150 LET e = INT(SQR(a)) + 2
160 LET f = 0
170 FOR n = i TO e STEP 2
180 IF a /n = INT(a/n) THEN LET a = a / n: LET i = n: LET n = e: LET f = 1
190 NEXT n
200 IF a > n AND f <> 0 THEN GOTO 160
210 PRINT a
220 END</syntaxhighlight>
{{out}}
<pre>6857</pre>
 
==={{header|BASIC256}}===
<syntaxhighlight lang="basic">#No primality testing is even required.
n = 600851475143
j = 3
do
if int(n/j) = n/j then n /= j
j += 2
until j = n
print n</syntaxhighlight>
{{out}}
<pre>6857</pre>
 
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
{{trans|Applesoft BASIC}}
<syntaxhighlight lang="basic">100 CLS : REM 10 HOME para Applesoft BASIC
110 LET a = 600851475143
120 LET f = 0
130 IF a/2 = INT(a/2) THEN LET a = a/2: LET f = 1: GOTO 130
140 LET i = 3
150 LET e = INT(SQR(a)) + 2
160 LET f = 0
170 FOR n = i TO e STEP 2
180 IF a /n = INT(a/n) THEN LET a = a / n: LET i = n: LET n = e: LET f = 1
190 NEXT n
200 IF a > n AND f <> 0 THEN GOTO 160
210 PRINT a
220 END</syntaxhighlight>
{{out}}
<pre>6857</pre>
 
==={{header|FreeBASIC}}===
<langsyntaxhighlight lang="freebasic">#include"isprime.bas"
dim as ulongint n = 600851475143, j = 3
while not isprime(n)
Line 56 ⟶ 201:
j+=2
wend
print n</langsyntaxhighlight>
{{out}}<pre>6857</pre>
 
==={{header|GW-BASIC}}===
No primality testing is even required.
<langsyntaxhighlight lang="gwbasic">10 N#=600851475143#
20 J#=3
30 IF J#=N# THEN GOTO 100
Line 67 ⟶ 212:
50 J#=J#+2
60 GOTO 30
100 PRINT N#</langsyntaxhighlight>
{{output}}<pre>6857</pre>
 
==={{header|QBasic}}===
{{works with|QBasic|1.1}}
{{works with|QuickBasic|4.5}}
<syntaxhighlight lang="qbasic">REM No primality testing is even required.
DIM a AS DOUBLE
a = 600851475143#
i = 3
DO
IF INT(a / i) = a / i THEN a = a / i
i = i + 2
LOOP UNTIL a = i ' o WHILE a <> i
PRINT a</syntaxhighlight>
{{out}}
<pre>6857</pre>
 
==={{header|Run BASIC}}===
<syntaxhighlight lang="vb">function isPrime(n)
if n < 2 then isPrime = 0 : goto [exit]
if n = 2 then isPrime = 1 : goto [exit]
if n mod 2 = 0 then isPrime = 0 : goto [exit]
isPrime = 1
for i = 3 to int(n^.5) step 2
if n mod i = 0 then isPrime = 0 : goto [exit]
next i
[exit]
end function
 
n = 600851475143
j = 3
while isPrime(n) <> 1
if n mod j = 0 then n = n / j
j = j +2
wend
print n
 
'But, no primality testing is even required.
n = 600851475143
j = 3
while j <> n
if int(n/j) = n / j then n = n / j
j = j +2
wend
print n
end</syntaxhighlight>
{{out}}
<pre>6857
6857</pre>
 
==={{header|True BASIC}}===
<syntaxhighlight lang="qbasic">!No primality testing is even required.
LET n = 600851475143
LET j = 3
DO WHILE j <> n
IF INT(n/j) = n / j THEN LET n = n / j
LET j = j + 2
LOOP
PRINT n
END</syntaxhighlight>
{{out}}
<pre>6857</pre>
 
==={{header|XBasic}}===
{{works with|Windows XBasic}}
<syntaxhighlight lang="qbasic">PROGRAM "LPF"
VERSION "0.0000"
 
DECLARE FUNCTION Entry ()
 
FUNCTION Entry ()
'No primality testing is even required.
DOUBLE n
n = 600851475143
j = 3
 
DO
IF INT(n/j) = n/j THEN n = n / j
j = j + 2
LOOP UNTIL j = n
PRINT n
END FUNCTION
END PROGRAM</syntaxhighlight>
{{out}}
<pre>6857</pre>
 
==={{header|Yabasic}}===
<syntaxhighlight lang="basic">//No primality testing is even required.
n = 600851475143
j = 3
repeat
if int(n/j) = n/j n = n / j
j = j + 2
until j = n
print n</syntaxhighlight>
{{out}}
<pre>6857</pre>
 
=={{header|BCPL}}==
This version creates a 2,3,5 wheel object, which is instantiated by the factorization routine.
<syntaxhighlight 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
}
</syntaxhighlight>
{{Out}}
<pre>
BCPL 64-bit Cintcode System (13 Jan 2020)
0.000> The largest prime factor of 600,851,475,143 is 6857
0.001>
</pre>
=={{header|C}}==
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
 
Line 93 ⟶ 390:
printf( "%ld\n", n );
return 0;
}</langsyntaxhighlight>
{{out}}<pre>6857</pre>
 
=={{header|CoffeeScript}}==
<syntaxhighlight 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)}"
</syntaxhighlight>
{{Out}}
<pre>
The largest prime factor of 600,851,475,143 is 6857
</pre>
 
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|Math,SysUtils,StdCtrls}}
 
 
<syntaxhighlight lang="Delphi">
function IsPrime(N: int64): boolean;
{Fast, optimised prime test}
var I,Stop: int64;
begin
if (N = 2) or (N=3) then Result:=true
else if (n <= 1) or ((n mod 2) = 0) or ((n mod 3) = 0) then Result:= false
else
begin
I:=5;
Stop:=Trunc(sqrt(N+0.0));
Result:=False;
while I<=Stop do
begin
if ((N mod I) = 0) or ((N mod (I + 2)) = 0) then exit;
Inc(I,6);
end;
Result:=True;
end;
end;
 
 
function GetLargestPrimeFact(N: int64): int64;
var J: int64;
begin
J:=3;
while not IsPrime(N) do
begin
if (N mod j) = 0 then N:=N div J;
Inc(J,2);
end;
Result:=N;
end;
 
 
procedure TestLargePrimeFact(Memo: TMemo);
var F: integer;
begin
F:=GetLargestPrimeFact(600851475143);
Memo.Lines.Add(IntToStr(F));
end;
 
 
</syntaxhighlight>
{{out}}
<pre>
6857
</pre>
 
 
=={{header|EasyLang}}==
<syntaxhighlight>
n = 600851475143
i = 2
while n > i
if n mod i = 0
n = n div i
.
i += 1
.
print n
</syntaxhighlight>
{{out}}
<pre>
6857
</pre>
 
=={{header|Elixir}}==
<syntaxhighlight 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)}"
</syntaxhighlight>
{{Out}}
<pre>
The largest prime factor of 600,851,475,143 is 6857
</pre>
 
=={{header|Erlang}}==
Uses a factorization wheel, but without builtin lazy lists, it's rather awkward for a functional language.
<syntaxhighlight 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).
</syntaxhighlight>
{{Out}}
<pre>
The largest prime factor of 600,851,475,143 is 6857
</pre>
 
=={{header|F_Sharp|F#}}==
<syntaxhighlight lang="fsharp">
printfn "%d" (Seq.last<|Open.Numeric.Primes.Prime.Factors 600851475143L)
</syntaxhighlight>
{{out}}
<pre>
6857
</pre>
 
=={{header|Factor}}==
<syntaxhighlight lang="factor">USING: math.primes.factors prettyprint sequences ;
 
600851475143 factors last .</syntaxhighlight>
 
=={{header|Fermat}}==
<langsyntaxhighlight lang="fermat">n:=600851475143;
j:=3;
while Isprime(n)<>1 do
Line 103 ⟶ 569:
j:=j+2;
od;
!!n;</langsyntaxhighlight>
{{out}}<pre>6857</pre>
 
=={{header|Go}}==
{{trans|Wren}}
<langsyntaxhighlight lang="go">package main
 
import "fmt"
Line 150 ⟶ 616:
n := uint64(600851475143)
fmt.Println("The largest prime factor of", n, "is", largestPrimeFactor(n), "\b.")
}</langsyntaxhighlight>
 
{{out}}
<pre>
The largest prime factor of 600851475143 is 6857.
</pre>
 
=={{header|J}}==
{{trans|jq}}<syntaxhighlight lang="j"> {:q:600851475143
6857</syntaxhighlight>
=={{header|jq}}==
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
 
Using `factors` as defined at [[Prime_decomposition#jq]]:
<syntaxhighlight lang="jq">600851475143 | last(factors)</syntaxhighlight>
{{out}}
<pre>
6857
</pre>
 
=={{header|Julia}}==
<langsyntaxhighlight lang="julia"> using Primes
 
@show first(last(factor(600851475143).pe))
</langsyntaxhighlight>{{out}}<pre>first(last((factor(600851475143)).pe)) = 6857</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">Max[FactorInteger[600851475143][[All, 1]]]</syntaxhighlight>
 
{{out}}<pre>
6857
</pre>
 
=={{header|PARI/GP}}==
<langsyntaxhighlight lang="parigp">A=factor(600851475143)
print(A[matsize(A)[1],1])</langsyntaxhighlight>
{{out}}<pre>6857</pre>
 
=={{header|Perl}}==
<langsyntaxhighlight lang="perl">use strict;
use warnings;
use feature 'say';
Line 178 ⟶ 664:
}
 
say +(f 600851475143)[-2]</langsyntaxhighlight>
{{out}}
<pre>6857</pre>
 
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<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>
<!--</syntaxhighlight>-->
{{out}}
<pre>
6857
</pre>
 
=={{header|PL/I}}==
Based on the Wren, Go and Algol 68 samples.
<langsyntaxhighlight lang="pli">/* find the largest prime factor of 600851475143 */
largestPrimeFactor: procedure options( main );
declare ( n, maxFactor, v, k, rootN ) decimal( 12 )fixed;
Line 207 ⟶ 703:
if v > 1 then maxFactor = v;
put skip list( 'Largest prime factor of ', n, ' is ', maxFactor );
end largestPrimeFactor;</langsyntaxhighlight>
{{out}}
<pre>
Largest prime factor of 600851475143 is 6857
</pre>
 
=={{header|Prolog}}==
<syntaxhighlight 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.
</syntaxhighlight>
{{Out}}
<pre>
The largest prime factor of 600,851,475,143 is 6857
</pre>
 
 
=={{header|Python}}==
<syntaxhighlight 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);</syntaxhighlight>
 
=={{header|Quackery}}==
 
<code>primefactors</code> is defined at [[Prime decomposition#Quackery]].
 
<syntaxhighlight lang="Quackery">600851475143 primefactors -1 peek echo</syntaxhighlight>
 
{{out}}
 
<pre>6857</pre>
 
=={{header|R}}==
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">
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")
 
</syntaxhighlight>
{{Out}}
<pre>
The prime factors of 600,851,475,143 are 71, 839, 1471, 6857
</pre>
 
Line 218 ⟶ 819:
===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.
<syntaxhighlight lang="raku" perl6line>use Prime::Factor;
 
my $start = now;
Line 225 ⟶ 826:
say "Largest prime factor of $_: ", max prime-factors $_;
last if now - $start > 1; # quit after one second of total run time
}</langsyntaxhighlight>
 
<pre>Largest prime factor of 600851475143: 6857
Line 326 ⟶ 927:
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).''
<syntaxhighlight lang="raku" perl6line>use Inline::Perl5;
my $p5 = Inline::Perl5.new();
$p5.use: 'ntheory';
Line 336 ⟶ 937:
say "Largest prime factor of $_: ", lpf "$_";
last if now - $start > 1; # quit after one second of total run time
}</langsyntaxhighlight>
Same output only much longer.
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
load "stdlib.ring"
see "working..." + nl
Line 359 ⟶ 960:
see "" + n + nl
see "done..." + nl
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 367 ⟶ 968:
done...
</pre>
 
=={{header|RPL}}==
{{works with|HP|49}}
The task can be solved directly by a command line:
600851475143 FACTORS 1 GET
{{out}}
<pre>1: 6857
</pre>
 
=={{header|Ruby}}==
<syntaxhighlight lang="ruby">require 'prime'
 
p 600851475143.prime_division.last.first</syntaxhighlight>
{{out}}
<pre>6857
</pre>
 
=={{header|Rust}}==
<syntaxhighlight lang="rust">
fn main( ) {
let mut current : i64 = 600851475143 ;
let mut latest_divisor : i64 = 2 ;
while current != 1 {
latest_divisor = 2 ;
while current % latest_divisor != 0 {
latest_divisor += 1 ;
}
current /= latest_divisor ;
}
println!("{}" , latest_divisor ) ;
}</syntaxhighlight>
{{out}}
<pre>
6857
</pre>
 
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">var n = 600851475143
 
say gpf(n) #=> 6857
say factor(n).last #=> 6857</syntaxhighlight>
 
=={{header|Wren}}==
Without using any library functions at all (it's a one-liner otherwise):
<langsyntaxhighlight ecmascriptlang="wren">var largestPrimeFactor = Fn.new { |n|
if (!n.isInteger || n < 2) return 1
var inc = [4, 2, 4, 2, 4, 6, 2, 6]
Line 401 ⟶ 1,043:
 
var n = 600851475143
System.print("The largest prime factor of %(n) is %(largestPrimeFactor.call(n)).")</langsyntaxhighlight>
 
{{out}}
Line 409 ⟶ 1,051:
 
=={{header|XPL0}}==
<langsyntaxhighlight XPL0lang="xpl0">real Num, Max, Div, Quot;
[Num:= 600851475143.;
Max:= 0.;
Line 425 ⟶ 1,067:
Format(1, 0);
RlOut(0, Max);
]</langsyntaxhighlight>
 
{{out}}
Chkas
1,983

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/316998...363876"