Fermat numbers: Difference between revisions
→{{header|langur}}
Langurmonkey (talk | contribs) |
Langurmonkey (talk | contribs) |
||
| (7 intermediate revisions by 2 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.
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 =
val .factors =
for[.f=[]] .i, .s = 2,
if .x div .i {
.f ~= [.i]
.x \= .i
.s =
}
} ~ [.x]
Line 1,301 ⟶ 1,393:
writeln "first 10 Fermat numbers"
for .i in 0..9 {
writeln
}
writeln()
Line 1,310 ⟶ 1,402:
val .fac = .factors(.ferm)
if len(.fac) == 1 {
writeln
} else {
writeln
}
}
▲}</syntaxhighlight>
</syntaxhighlight>
{{out}}
<pre>first 10 Fermat numbers
F₀ = 3
| |||