First 9 prime Fibonacci number: Difference between revisions
→{{header|Python}}
(add RPL) |
Hellangelx (talk | contribs) |
||
Line 1,408:
=={{header|Python}}==
<syntaxhighlight lang="python">
2 things:
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.
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
start = time()▼
def miller_rabin(n, k=5):
▲ if x < 2:
return False
r, s = 0,
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):
return "%s...%s (Total %d digits)" % (s[:10], s[-10:], len(s))
▲while len(f) < n:
▲ if prime(b):
▲ f.append(b)
def prime_fibonacci(n):
print("fib(%d): %s (%s s)" % (fibn, b, time() - start))▼
fibn = 2
odd_count = 0
▲ start = time()
while n > 0:
if a == 2 or (a % 2 != 0 and miller_rabin(a)):
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,448 ⟶ 1,488:
fib(17): 1597 (0.0 s)
fib(23): 28657 (0.0 s)
fib(29): 514229 (0.
fib(43): 433494437 (0.
fib(47): 2971215073 (0.
fib(83): 99194853094755497 (
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)
</pre>
| |||