Fermat numbers: Difference between revisions
→{{header|langur}}
m (→{{header|Wren}}: Minor tidy) |
Langurmonkey (talk | contribs) |
||
| (8 intermediate revisions by 3 users not shown) | |||
Line 24:
<br>
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
Uses Algol 68G's LONG LONG INT which has programmer specifiable precision.
{{libheader|ALGOL 68-primes}}
The source of primes.incl.a68 is on another page on Rosetta Code, see the above link.
<syntaxhighlight lang="algol68">
BEGIN # find and factorise some Fermat numbers: F(n) = 2^(2^n) + 1 #
PR read "primes.incl.a68" PR # include prime utilities #
PR precision 256 PR # set the precision of LONG LONG INT #
PROC gcd = ( LONG LONG INT x, y )LONG LONG INT: # iterative gcd #
BEGIN
LONG LONG INT a := x, b := y;
WHILE b /= 0 DO
LONG LONG INT next a = b;
b := a MOD b;
a := next a
OD;
ABS a
END # gcd # ;
# returns a prime factor (if possible) of n, if n is prime, n is returned #
PROC pollard rho = ( LONG LONG INT n )LONG LONG INT:
IF is probably prime( n )
THEN n
ELIF LONG LONG INT x := 2, y := 2, d := 1;
PROC g = ( LONG LONG INT x )LONG LONG INT: ( ( x * x ) + 1 ) MOD n;
WHILE d = 1 DO
x := g( x );
y := g( g( y ) );
d := gcd( ABS( x - y ), n )
OD;
d = n
THEN print( ( "pollard rho found non probably prime n for: ", n, newline ) );
n
ELIF LONG LONG INT other d = n OVER d;
d > other d
THEN other d
ELSE d
FI # pollard rho # ;
# returns the lowest prime factor of n, or n if n is prime #
PROC prime factor = ( LONG LONG INT n )LONG LONG INT:
IF LONG LONG INT d := pollard rho( n );
d = n
THEN d
ELSE # check for a lower factor #
LONG LONG INT other d := n OVER d;
LONG LONG INT d1 := pollard rho( other d );
WHILE d1 < d DO
d := d1;
other d := other d OVER d;
d1 := pollard rho( other d )
OD;
IF d1 < d THEN d1 ELSE d FI
FI # prime factor # ;
# task #
INT p2 := 1;
FOR i FROM 0 TO 9 DO
LONG LONG INT fn = 1 + ( LONG LONG 2 )^p2;
print( ( "F(", whole( i, 0 ), "): ", whole( fn, 0 ) ) );
IF i < 7 THEN
print( ( ", " ) );
LONG LONG INT pf = prime factor( fn );
IF pf = fn THEN
print( ( "prime" ) )
ELSE
print( ( whole( pf, 0 ), " x ", whole( fn OVER pf, 0 ) ) )
FI
FI;
print( ( newline ) );
p2 *:= 2
OD
END
</syntaxhighlight>
{{out}}
<pre>
F(0): 3, prime
F(1): 5, prime
F(2): 17, prime
F(3): 257, prime
F(4): 65537, prime
F(5): 4294967297, 641 x 6700417
F(6): 18446744073709551617, 274177 x 67280421310721
F(7): 340282366920938463463374607431768211457
F(8): 115792089237316195423570985008687907853269984665640564039457584007913129639937
F(9): 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097
</pre>
=={{header|Arturo}}==
Line 1,287 ⟶ 1,379:
=={{header|langur}}==
{{trans|Python}}
<syntaxhighlight lang="langur">val .fermat = fn(.i) { 2 ^ 2 ^ .i + 1 }
val .factors =
for[.f=[]] .i, .s = 2,
if .x div .i {
.f ~= [.i]
.x \= .i
.s =
}
} ~ [.x]
Line 1,319 ⟶ 1,410:
{{out}}
<pre>first 10 Fermat numbers
F₀ = 3
Line 1,515 ⟶ 1,605:
Pollard rho try factor 350001591824186871106763863899530746217943677302816436473017740242946077356624684213115564488348300185108877411543625345263121839042445381828217455916005721464151569276047005167043946981206545317048033534893189043572263100806868980998952610596646556521480658280419327021257968923645235918768446677220584153297488306270426504473941414890547838382804073832577020334339845312084285496895699728389585187497914849919557000902623608963141559444997044721763816786117073787751589515083702681348245404913906488680729999788351730419178916889637812821243344085799435845038164784900107242721493170135785069061880328434342030106354742821995535937481028077744396075726164309052460585559946407282864168038994640934638329525854255227752926198464207255983432778402344965903148839661825873175277621985527846249416909718758069997783882773355041329208102046913755441975327368023946523920699020098723785533557579080342841062805878477869513695185309048285123705067072486920463781103076554014502567884803571416673251784936825115787932810954867447447568320403976197134736485611912650805539603318790667901618038578533362100071745480995207732506742832634459994375828162163700807237997808869771569154136465922798310222055287047244647419069003284481 elapsed time = 114 ms (factor = 63766529).
F₁₂ = 114689 * 26017793 * 63766529 * (C1213)</pre>
=={{header|PARI/GP}}==
{{trans|Julia}}
<syntaxhighlight lang="PARI/GP">
\\ Define a function to calculate Fermat numbers
fermat(n) = 2^(2^n) + 1;
\\ Define a function to factor Fermat numbers up to a given maximum
\\ and optionally just print them without factoring
factorfermats(mymax, nofactor=0) =
{
local(fm, factors, n);
for (n = 0, mymax,
fm = fermat(n);
if (nofactor,
print("Fermat number F(", n, ") is ", fm, ".");
next;
);
factors = factorint(fm);
if (matsize(factors)[1] == 1 && factors[1,2] == 1, \\ Check if it has only one factor with exponent 1 (i.e., prime)
print("Fermat number F(", n, "), ", fm, ", is prime.");
,
print("Fermat number F(", n, "), ", fm, ", factors to ", (factors), ".");
);
);
}
{
\\ Example usage
factorfermats(9, 1); \\ Print Fermat numbers without factoring
print(""); \\ Just to add a visual separator in the output
factorfermats(10); \\ Factor Fermat numbers
}
</syntaxhighlight>
{{out}}
<pre>
Fermat number F(0) is 3.
Fermat number F(1) is 5.
Fermat number F(2) is 17.
Fermat number F(3) is 257.
Fermat number F(4) is 65537.
Fermat number F(5) is 4294967297.
Fermat number F(6) is 18446744073709551617.
Fermat number F(7) is 340282366920938463463374607431768211457.
Fermat number F(8) is 115792089237316195423570985008687907853269984665640564039457584007913129639937.
Fermat number F(9) is 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097.
Fermat number F(0), 3, is prime.
Fermat number F(1), 5, is prime.
Fermat number F(2), 17, is prime.
Fermat number F(3), 257, is prime.
Fermat number F(4), 65537, is prime.
Fermat number F(5), 4294967297, factors to [641, 1; 6700417, 1].
Fermat number F(6), 18446744073709551617, factors to [274177, 1; 67280421310721, 1].
Fermat number F(7), 340282366920938463463374607431768211457, factors to [59649589127497217, 1; 5704689200685129054721, 1].
Fermat number F(8), 115792089237316195423570985008687907853269984665640564039457584007913129639937, factors to [1238926361552897, 1; 93461639715357977769163558199606896584051237541638188580280321, 1].
</pre>
=={{header|Perl}}==
| |||