First 9 prime Fibonacci number: Difference between revisions

Content added Content deleted
(add RPL)
Line 1,408: Line 1,408:
=={{header|Python}}==
=={{header|Python}}==
<syntaxhighlight lang="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
return False
if x == 2 or x == 3:
for p in [2, 3, 5, 7, 11]:
return True
if n < p * p:
if x % 2 == 0:
return True
return False
if n % p == 0:
for i in range(3, int(sqrt(x)) + 1, 2):
return False
if x % i == 0:
r, s = 0, n - 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 False
return True
return True




def format_large_number(n):
a, b, = 1, 1
fibn = 3
s = str(n)
⚫
if len(s) > 50:
f = []
return "%s...%s (Total %d digits)" % (s[:10], s[-10:], len(s))
⚫
while len(f) < n:
a, b, = b, a + b
return s

⚫
if prime(b):

⚫
f.append(b)
def prime_fibonacci(n):
⚫
print("fib(%d): %s (%s s)" % (fibn, b, time() - start))
fibn += 1
a, 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>
</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>

fib(3): 2 (0.0 s)
fib(3): 2 (0.0 s)
fib(4): 3 (0.0 s)
fib(4): 3 (0.0 s)
Line 1,448: Line 1,488:
fib(17): 1597 (0.0 s)
fib(17): 1597 (0.0 s)
fib(23): 28657 (0.0 s)
fib(23): 28657 (0.0 s)
fib(29): 514229 (0.0009968280792236328 s)
fib(29): 514229 (0.0 s)
fib(43): 433494437 (0.0009968280792236328 s)
fib(43): 433494437 (0.0 s)
fib(47): 2971215073 (0.003988504409790039 s)
fib(47): 2971215073 (0.0 s)
fib(83): 99194853094755497 (15.122319459915161 s)
fib(83): 99194853094755497 (0.0009968280792236328 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>
</pre>
Retrieved from "https://rosettacode.org/wiki/First_9_prime_Fibonacci_number"