Rosetta Code

First 9 prime Fibonacci number: Difference between revisions

Page Discussion

First 9 prime Fibonacci number (view source)

Revision as of 13:04, 5 May 2024

9,744 bytes added ,  14 days ago
Added Oberon-07
(→‎OCaml: add)
(Added Oberon-07)
 
(16 intermediate revisions by 11 users not shown)
Line 45:
fib(47): 2971215073
</pre>
 
=={{header|ABC}}==
<syntaxhighlight lang="abc">HOW TO REPORT prime n:
REPORT n>=2 AND NO d IN {2..floor (root n)} HAS n mod d = 0
 
PUT 1, 1 IN a, b
PUT 0 IN n
WHILE n<9:
IF prime a:
WRITE a/
PUT n+1 IN n
PUT b, a+b IN a, b</syntaxhighlight>
{{out}}
<pre>2
3
5
13
89
233
1597
28657
514229</pre>
 
=={{header|Ada}}==
Line 167 ⟶ 189:
2 3 5 13 89 233 1597 28657 514229
</pre>
 
=={{header|Arturo}}==
 
<syntaxhighlight lang="arturo">fib: $[x][
if? x<2 [1]
else [(fib x-1) + (fib x-2)]
]
 
firstPrimeFibos: select.first:9 2..∞ 'n -> prime? fib n
 
loop firstPrimeFibos 'f ->
print ["F(" ++ (to :string f+1) ++ ") =" fib f]</syntaxhighlight>
 
{{out}}
 
<pre>F(3) = 2
F(4) = 3
F(5) = 5
F(7) = 13
F(11) = 89
F(13) = 233
F(17) = 1597
F(23) = 28657
F(29) = 514229</pre>
 
=={{header|AWK}}==
Line 206 ⟶ 252:
2 3 5 13 89 233 1597 28657 514229
</pre>
 
 
=={{header|BASIC}}==
Line 422 ⟶ 467:
<syntaxhighlight lang="cpp">#include <chrono>
#include <iostream>
#include <sstream>
#include <utility>
#include <primesieve.hpp>
Line 474 ⟶ 518:
std::string to_string(const big_int& n) {
std::string str = n.get_str();
ifsize_t len = (str.size() > 40) {;
if (len > 40) {
std::ostringstream os;
os << str.substrreplace(020, 20)len <<- 40, "..." << str.substr(str.size() - 20) << " (";
<< str.size() <<+= " digits)(";
return os.str += std::to_string(len);
str += " digits)";
}
return str;
Line 729 ⟶ 774:
28657
514229</pre>
 
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
 
<syntaxhighlight lang="Delphi">
function IsPrime(N: integer): boolean;
{Fast, optimised prime test}
var I,Stop: integer;
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));
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;
 
 
procedure ShowFibonacciPrimes(Memo: TMemo);
{Find and display first nine Fibonacci primes}
var N1,N2,T,Cnt: integer;
begin
Cnt:=0;
N1:=0; N2:=1;
while true do
begin
{Calculate next Fib number}
T:=N1+N2;
N1:=N2; N2:=T;
{Test if it is prime}
if IsPrime(N2) then
begin
Inc(Cnt);
Memo.Lines.Add(IntToStr(N2));
if Cnt>=9 then break;
end;
end;
end;
</syntaxhighlight>
{{out}}
<pre>
2
3
5
13
89
233
1597
28657
514229
</pre>
 
=={{header|Draco}}==
Line 776 ⟶ 881:
28657
514229</pre>
 
=={{header|EasyLang}}==
<syntaxhighlight>
fastfunc isprim num .
i = 2
while i <= sqrt num
if num mod i = 0
return 0
.
i += 1
.
return 1
.
prev = 1
val = 1
while cnt < 9
h = prev + val
prev = val
val = h
if isprim val = 1
write val & " "
cnt += 1
.
.
</syntaxhighlight>
{{out}}
<pre>
2 3 5 13 89 233 1597 28657 514229
</pre>
 
=={{header|F_Sharp|F#}}==
Line 830 ⟶ 964:
514229
</pre>
 
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
include "NSLog.incl"
 
 
local fn IsPrime( n as UInt64 ) as BOOL
UInt64 i
BOOL result
if ( n < 2 ) then result = NO : exit fn
for i = 2 to n + 1
if ( i * i <= n ) and ( n mod i == 0 ) then result = NO : exit fn
next
result = YES
end fn = result
 
 
void local fn FindFibonacciPrimes( limit as long )
UInt64 f1 = 1, f2 = 1, f3
long count = 0
NSLog( @"The first %d prime Fibonacci numbers are:\n", limit )
while ( count < limit )
f3 = f1 + f2
if ( fn IsPrime( f3 ) )
NSLog( @"%ld ", f3 )
count++
end if
f1 = f2
f2 = f3
wend
NSLog( @"\n" )
end fn
 
fn FindFibonacciPrimes( 10 )
 
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
The first 10 prime Fibonacci numbers are:
 
2
3
5
13
89
233
1597
28657
514229
433494437
</pre>
 
 
=={{header|Go}}==
Line 1,081 ⟶ 1,272:
25 F(9311) = 34232 … 76289 (1946 digits)
26 F(9677) = 10565 … 70357 (2023 digits)</pre>
 
=={{header|Miranda}}==
<syntaxhighlight lang="miranda">main :: [sys_message]
main = [(Stdout . lay . map show . take 9 . filter prime) fibo]
 
fibo :: [num]
fibo = 1 : 1 : [a + b | (a,b) <- zip2 fibo (tl fibo)]
 
prime :: num->bool
prime n = n=2 \/ n=3, if n<=4
prime n = False, if or [n mod 2=0, n mod 3=0]
prime n = and [n mod d ~= 0 | d <- [3, 5..entier (sqrt n)]]</syntaxhighlight>
{{out}}
<pre>2
3
5
13
89
233
1597
28657
514229</pre>
 
=={{header|Nim}}==
<syntaxhighlight lang="Nim">func isPrime(n: Natural): bool =
## Return "true" is "n" is prime.
if n < 2: return false
if (n and 1) == 0: return n == 2
if n mod 3 == 0: return n == 3
var d = 5
var step = 2
while d * d <= n:
if n mod d == 0:
return false
inc d, step
step = 6 - step
return true
 
iterator fib(): int =
var prev = 0
var curr = 1
while true:
yield curr
swap prev, curr
inc curr, prev
 
echo "The first 9 prime Fibonacci numbers are:"
var count = 0
for n in fib():
if n.isPrime:
stdout.write n, ' '
inc count
if count == 9:
echo()
break
</syntaxhighlight>
 
{{out}}
<pre>The first 9 prime Fibonacci numbers are:
2 3 5 13 89 233 1597 28657 514229
</pre>
 
=={{header|Oberon-07}}==
<syntaxhighlight lang="modula2">
MODULE PrimeFibonacciNumbers; (* show the first 9 prime fibonacci numbers *)
IMPORT Out, Math;
 
CONST toFind = 9;
VAR pCount, prev, curr, next :INTEGER;
 
(* returns true if n is prime, false otherwise - uses trial division *)
PROCEDURE isPrime( n :INTEGER ):BOOLEAN;
VAR i, rootN :INTEGER;
prime :BOOLEAN;
BEGIN
IF n < 3 THEN prime := n = 2
ELSIF ~ ODD( n ) THEN prime := FALSE
ELSE
prime := TRUE;
i := 3;
rootN := FLOOR( Math.sqrt( FLT( n ) ) );
WHILE ( i <= rootN ) & prime DO
prime := n MOD i # 0;
i := i + 2
END
END
RETURN prime
END isPrime ;
 
BEGIN
pCount := 0;
prev := 0;
curr := 1;
WHILE pCount < toFind DO
next := prev + curr;
prev := curr;
curr := next;
IF isPrime( curr ) THEN
pCount := pCount + 1;
Out.String( " " );Out.Int( curr, 0 )
END
END
END PrimeFibonacciNumbers.
</syntaxhighlight>
{{out}}
<pre>
2 3 5 13 89 233 1597 28657 514229
</pre>
 
=={{header|OCaml}}==
Line 1,229 ⟶ 1,528:
=={{header|Python}}==
<syntaxhighlight lang="python">
2 things:
from math import sqrt
"""for the Fibonacci sequence: an even number is following after 2 odd numbers. Eliminate time to check whether it is prime or not because even numbers are not primes.
from time import time
for prime numbers: it becomes bigger and bigger. The original algorithm will be slow for super big number. In this case, I use Miller Rabin primality test.
 
P/S: I am not surprised. It is fast but still cannot compare to other languages such as C++ or Rust or .... After all, Python is still slow :P"""
n = 12
start = time()
 
def miller_rabin(n, k=5):
 
if n < 2:
def prime(x):
if x < 2:
return False
iffor xp ==in [2, or3, x5, ==7, 311]:
returnif Truen < p * p:
if x % 2 == 0: return True
returnif Falsen % p == 0:
for i in range(3, int(sqrt(x)) + 1, 2): return False
r, s = 0, ifn x- % i == 0:1
while s % 2 == 0:
r += 1
s //= 2
for _ in range(k):
a = random.randint(2, n - 1)
x = pow(a, s, n)
if x == 1 or x == n - 1:
continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1:
break
else:
return False
return True
 
 
def format_large_number(n):
a, b, = 1, 1
fibn s = 3str(n)
if len(s) > 50:
f = []
return "%s...%s (Total %d digits)" % (s[:10], s[-10:], len(s))
while len(f) < n:
a,return b, = b, a + bs
 
if prime(b):
 
f.append(b)
def prime_fibonacci(n):
print("fib(%d): %s (%s s)" % (fibn, b, time() - start))
fibna, b += 1, 1
fibn = 2
odd_count = 0
start = time()
 
while n > 0:
if a == 2 or (a % 2 != 0 and miller_rabin(a)):
print("fib(%d): %s (%s s)" % (fibn - 1, format_large_number(a), time() - start))
n -= 1
if a % 2 != 0:
odd_count += 1
else:
odd_count = 0
else:
odd_count = 0
 
if odd_count == 2:
a, b = b, a + b
fibn += 1
odd_count = 1
continue
 
a, b = b, a + b
fibn += 1
 
 
prime_fibonacci(26)
 
</syntaxhighlight>
{{out}}
<pre>
 
fib(3): 2 (0.0 s)
fib(4): 3 (0.0 s)
Line 1,269 ⟶ 1,608:
fib(17): 1597 (0.0 s)
fib(23): 28657 (0.0 s)
fib(29): 514229 (0.00099682807922363280 s)
fib(43): 433494437 (0.00099682807922363280 s)
fib(47): 2971215073 (0.0039885044097900390 s)
fib(83): 99194853094755497 (150.1223194599151610009968280792236328 s)
fib(131): 1066340417491710595814572169 (0.0009968280792236328 s)
fib(137): 19134702400093278081449423917 (0.0009968280792236328 s)
fib(359): 4754204377...6935476241 (Total 75 digits) (0.009973287582397461 s)
fib(431): 5298927110...9676262369 (Total 90 digits) (0.017951488494873047 s)
fib(433): 1387277127...3712568353 (Total 91 digits) (0.018948078155517578 s)
fib(449): 3061719992...2805665949 (Total 94 digits) (0.021939992904663086 s)
fib(509): 1059799926...9876129909 (Total 107 digits) (0.034908294677734375 s)
fib(569): 3668447431...7781065869 (Total 119 digits) (0.0468745231628418 s)
fib(571): 9604120061...3008074629 (Total 119 digits) (0.050863027572631836 s)
fib(2971): 3571035606...8470316229 (Total 621 digits) (9.068741798400879 s)
fib(4723): 5001956361...0053591957 (Total 987 digits) (52.320056200027466 s)
fib(5387): 2930441286...4725855833 (Total 1126 digits) (86.49367618560791 s)
fib(9311): 3423208606...4669476289 (Total 1946 digits) (686.371306180954 s)
fib(9677): 1056597787...4550670357 (Total 2023 digits) (795.5426495075226 s)
 
Process finished with exit code 0
 
</pre>
Line 1,320 ⟶ 1,672:
20: 36684474316080978061473613646275630451100586901195229815270242868417768061193560857904335017879540515228143777781065869</pre>
 
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
= <Prout <Gen 9 Prime Fibo (1 1)>>;
}
 
Gen {
0 s.Filter s.Gen (e.State) = ;
s.N s.Filter s.Gen (e.State),
<Mu s.Gen (e.State)>: (e.Next) e.Val,
<Mu s.Filter e.Val>: {
True = e.Val <Gen <- s.N 1> s.Filter s.Gen (e.Next)>;
False = <Gen s.N s.Filter s.Gen (e.Next)>;
};
};
 
Fibo {
(s.A s.B) = (s.B <+ s.A s.B>) s.A;
};
 
Prime {
0 = False; 1 = False;
2 = True; 3 = True;
s.N, <Mod s.N 2>: 0 = False;
s.N, <Mod s.N 3>: 0 = False;
s.N = <Prime1 s.N 5>;
};
 
Prime1 {
s.N s.D, <Compare s.N <* s.D s.D>>: '-' = True;
s.N s.D, <Mod s.N s.D>: 0 = False;
s.N s.D = <Prime1 s.N <+ 2 s.D>>;
};</syntaxhighlight>
{{out}}
<pre>2 3 5 13 89 233 1597 28657 514229</pre>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
Line 1,450 ⟶ 1,836:
elapsed time: 22642 milliseconds
</pre>
 
=={{header|RPL}}==
≪ { } 0 1
'''WHILE''' 3 PICK SIZE 9 < '''REPEAT'''
SWAP OVER +
'''IF''' DUP ISPRIME? '''THEN''' ROT OVER + UNROT '''END'''
'''END''' DROP2
≫ '<span style="color:blue">TASK</span>' STO
{{out}}
<pre>
1: { 2 3 5 13 89 233 1597 28657 514229 }
</pre>
 
=={{header|Ruby}}==
<syntaxhighlight lang="ruby">require 'prime'
 
prime_fibs = Enumerator.new do |y|
a, b = 1, 1
loop do
y << a if a.prime?
a, b = b, a + b
end
end
puts prime_fibs.take(9)</syntaxhighlight>
{{out}}
<pre>
[2, 3, 5, 13, 89, 233, 1597, 28657, 514229]
</pre>
 
=={{header|SETL}}==
<syntaxhighlight lang="setl">program prime_fibonacci;
[a, b] := [1, 1];
loop until seen = 9 do
if prime a then
print(a);
seen +:= 1;
end if;
[a, b] := [b, a+b];
end loop;
 
op prime(n);
if n<=4 then
return n in {2, 3};
end if;
if n mod 2 = 0 or n mod 3 = 0 then
return false;
end if;
d := 5;
loop while d*d <= n do
if n mod d = 0 then return false; end if;
d +:= 2;
if n mod d = 0 then return false; end if;
d +:= 4;
end loop;
return true;
end op;
end program;</syntaxhighlight>
{{out}}
<pre>2
3
5
13
89
233
1597
28657
514229</pre>
 
=={{header|Sidef}}==
Line 1,460 ⟶ 1,913:
=={{header|Wren}}==
{{libheader|Wren-math}}
<syntaxhighlight lang="ecmascriptwren">import "./math" for Int
 
var limit = 11 // as far as we can go without using BigInt
Tigerofdarkness
3,025

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/335327...364240"