First 9 prime Fibonacci number: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (Thundergnat moved page First 9 Prime Fibonacci Number to First 9 prime Fibonacci number: capitalization policy) |
(Added C++, Java and Rust solutions) |
||
Line 273: | Line 273: | ||
The first 12 prime Fibonacci numbers are: |
The first 12 prime Fibonacci numbers are: |
||
2 3 5 13 89 233 1597 28657 514229 433494437 2971215073 99194853094755497 |
2 3 5 13 89 233 1597 28657 514229 433494437 2971215073 99194853094755497 |
||
</pre> |
|||
=={{header|C++}}== |
|||
{{libheader|GMP}} |
|||
{{libheader|Primesieve}} |
|||
<lang cpp>#include <chrono> |
|||
#include <iostream> |
|||
#include <sstream> |
|||
#include <utility> |
|||
#include <primesieve.hpp> |
|||
#include <gmpxx.h> |
|||
using big_int = mpz_class; |
|||
bool is_probably_prime(const big_int& n) { |
|||
return mpz_probab_prime_p(n.get_mpz_t(), 30) != 0; |
|||
} |
|||
class prime_fibonacci_generator { |
|||
public: |
|||
prime_fibonacci_generator(); |
|||
std::pair<uint64_t, big_int> next(); |
|||
private: |
|||
big_int next_fibonacci(); |
|||
primesieve::iterator p_; |
|||
big_int f0_ = 0; |
|||
big_int f1_ = 1; |
|||
uint64_t n_ = 0; |
|||
}; |
|||
prime_fibonacci_generator::prime_fibonacci_generator() { |
|||
for (int i = 0; i < 2; ++i) |
|||
p_.next_prime(); |
|||
} |
|||
std::pair<uint64_t, big_int> prime_fibonacci_generator::next() { |
|||
for (;;) { |
|||
if (n_ > 4) { |
|||
uint64_t p = p_.next_prime(); |
|||
for (; p > n_; ++n_) |
|||
next_fibonacci(); |
|||
} |
|||
++n_; |
|||
big_int f = next_fibonacci(); |
|||
if (is_probably_prime(f)) |
|||
return {n_ - 1, f}; |
|||
} |
|||
} |
|||
big_int prime_fibonacci_generator::next_fibonacci() { |
|||
big_int result = f0_; |
|||
big_int f = f0_ + f1_; |
|||
f0_ = f1_; |
|||
f1_ = f; |
|||
return result; |
|||
} |
|||
std::string to_string(const big_int& n) { |
|||
std::string str = n.get_str(); |
|||
if (str.size() > 40) { |
|||
std::ostringstream os; |
|||
os << str.substr(0, 20) << "..." << str.substr(str.size() - 20) << " (" |
|||
<< str.size() << " digits)"; |
|||
return os.str(); |
|||
} |
|||
return str; |
|||
} |
|||
int main() { |
|||
auto start = std::chrono::high_resolution_clock::now(); |
|||
prime_fibonacci_generator gen; |
|||
for (int i = 1; i <= 26; ++i) { |
|||
auto [n, f] = gen.next(); |
|||
std::cout << i << ": F(" << n << ") = " << to_string(f) << '\n'; |
|||
} |
|||
auto finish = std::chrono::high_resolution_clock::now(); |
|||
std::chrono::duration<double> ms(finish - start); |
|||
std::cout << "elapsed time: " << ms.count() << " seconds\n"; |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
1: F(3) = 2 |
|||
2: F(4) = 3 |
|||
3: F(5) = 5 |
|||
4: F(7) = 13 |
|||
5: F(11) = 89 |
|||
6: F(13) = 233 |
|||
7: F(17) = 1597 |
|||
8: F(23) = 28657 |
|||
9: F(29) = 514229 |
|||
10: F(43) = 433494437 |
|||
11: F(47) = 2971215073 |
|||
12: F(83) = 99194853094755497 |
|||
13: F(131) = 1066340417491710595814572169 |
|||
14: F(137) = 19134702400093278081449423917 |
|||
15: F(359) = 47542043773469822074...62268716376935476241 (75 digits) |
|||
16: F(431) = 52989271100609562179...55134424689676262369 (90 digits) |
|||
17: F(433) = 13872771278047838271...25954602593712568353 (91 digits) |
|||
18: F(449) = 30617199924845450305...49015933442805665949 (94 digits) |
|||
19: F(509) = 10597999265301490732...54396195769876129909 (107 digits) |
|||
20: F(569) = 36684474316080978061...15228143777781065869 (119 digits) |
|||
21: F(571) = 96041200618922553823...31637646183008074629 (119 digits) |
|||
22: F(2971) = 35710356064190986072...48642001438470316229 (621 digits) |
|||
23: F(4723) = 50019563612695729290...02854387700053591957 (987 digits) |
|||
24: F(5387) = 29304412869392580554...82040327194725855833 (1126 digits) |
|||
25: F(9311) = 34232086066590238613...37580645424669476289 (1946 digits) |
|||
26: F(9677) = 10565977873308861656...95169792504550670357 (2023 digits) |
|||
elapsed time: 21.8042 seconds |
|||
</pre> |
</pre> |
||
Line 641: | Line 750: | ||
28657 |
28657 |
||
514229 |
514229 |
||
</pre> |
|||
=={{header|Java}}== |
|||
Uses the PrimeGenerator class from [[Extensible prime generator#Java]]. |
|||
<lang java>import java.math.BigInteger; |
|||
public class PrimeFibonacciGenerator { |
|||
private PrimeGenerator primeGen = new PrimeGenerator(10000, 200000); |
|||
private BigInteger f0 = BigInteger.ZERO; |
|||
private BigInteger f1 = BigInteger.ONE; |
|||
private int index = 0; |
|||
public static void main(String[] args) { |
|||
PrimeFibonacciGenerator gen = new PrimeFibonacciGenerator(); |
|||
long start = System.currentTimeMillis(); |
|||
for (int i = 1; i <= 26; ++i) { |
|||
BigInteger f = gen.next(); |
|||
System.out.printf("%d: F(%d) = %s\n", i, gen.index - 1, toString(f)); |
|||
} |
|||
long finish = System.currentTimeMillis(); |
|||
System.out.printf("elapsed time: %g seconds\n", (finish - start)/1000.0); |
|||
} |
|||
private PrimeFibonacciGenerator() { |
|||
for (int i = 0; i < 2; ++i) |
|||
primeGen.nextPrime(); |
|||
} |
|||
private BigInteger next() { |
|||
for (;;) { |
|||
if (index > 4) { |
|||
int p = primeGen.nextPrime(); |
|||
for (; p > index; ++index) |
|||
nextFibonacci(); |
|||
} |
|||
++index; |
|||
BigInteger f = nextFibonacci(); |
|||
if (f.isProbablePrime(30)) |
|||
return f; |
|||
} |
|||
} |
|||
private BigInteger nextFibonacci() { |
|||
BigInteger result = f0; |
|||
BigInteger f = f0.add(f1); |
|||
f0 = f1; |
|||
f1 = f; |
|||
return result; |
|||
} |
|||
private static String toString(BigInteger f) { |
|||
String str = f.toString(); |
|||
if (str.length() > 40) { |
|||
StringBuilder s = new StringBuilder(str.substring(0, 20)); |
|||
s.append("..."); |
|||
s.append(str.substring(str.length() - 20)); |
|||
s.append(" ("); |
|||
s.append(str.length()); |
|||
s.append(" digits)"); |
|||
str = s.toString(); |
|||
} |
|||
return str; |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
1: F(3) = 2 |
|||
2: F(4) = 3 |
|||
3: F(5) = 5 |
|||
4: F(7) = 13 |
|||
5: F(11) = 89 |
|||
6: F(13) = 233 |
|||
7: F(17) = 1597 |
|||
8: F(23) = 28657 |
|||
9: F(29) = 514229 |
|||
10: F(43) = 433494437 |
|||
11: F(47) = 2971215073 |
|||
12: F(83) = 99194853094755497 |
|||
13: F(131) = 1066340417491710595814572169 |
|||
14: F(137) = 19134702400093278081449423917 |
|||
15: F(359) = 47542043773469822074...62268716376935476241 (75 digits) |
|||
16: F(431) = 52989271100609562179...55134424689676262369 (90 digits) |
|||
17: F(433) = 13872771278047838271...25954602593712568353 (91 digits) |
|||
18: F(449) = 30617199924845450305...49015933442805665949 (94 digits) |
|||
19: F(509) = 10597999265301490732...54396195769876129909 (107 digits) |
|||
20: F(569) = 36684474316080978061...15228143777781065869 (119 digits) |
|||
21: F(571) = 96041200618922553823...31637646183008074629 (119 digits) |
|||
22: F(2971) = 35710356064190986072...48642001438470316229 (621 digits) |
|||
23: F(4723) = 50019563612695729290...02854387700053591957 (987 digits) |
|||
24: F(5387) = 29304412869392580554...82040327194725855833 (1126 digits) |
|||
25: F(9311) = 34232086066590238613...37580645424669476289 (1946 digits) |
|||
26: F(9677) = 10565977873308861656...95169792504550670357 (2023 digits) |
|||
elapsed time: 53.7480 seconds |
|||
</pre> |
</pre> |
||
Line 826: | Line 1,029: | ||
2 3 5 13 89 233 1597 28657 514229 |
2 3 5 13 89 233 1597 28657 514229 |
||
done... |
done... |
||
</pre> |
|||
=={{header|Rust}}== |
|||
<lang rust>// [dependencies] |
|||
// rug = "1.15.0" |
|||
// primal = "0.3" |
|||
use rug::{Assign, Integer}; |
|||
fn fibonacci() -> impl std::iter::Iterator<Item = Integer> { |
|||
let mut f0 = Integer::from(0); |
|||
let mut f1 = Integer::from(1); |
|||
std::iter::from_fn(move || { |
|||
let result = Integer::from(&f0); |
|||
let f = Integer::from(&f0 + &f1); |
|||
f0.assign(&f1); |
|||
f1.assign(&f); |
|||
Some(result) |
|||
}) |
|||
} |
|||
fn prime_fibonacci() -> impl std::iter::Iterator<Item = (usize, Integer)> { |
|||
use rug::integer::IsPrime; |
|||
let mut primes = primal::Primes::all().skip(2); |
|||
let mut fib = fibonacci(); |
|||
let mut n = 0; |
|||
std::iter::from_fn(move || loop { |
|||
if n > 4 { |
|||
let p = primes.next().unwrap(); |
|||
while p > n { |
|||
fib.next(); |
|||
n += 1; |
|||
} |
|||
} |
|||
n += 1; |
|||
if let Some(f) = fib.next() { |
|||
if f.is_probably_prime(30) != IsPrime::No { |
|||
return Some((n - 1, f)); |
|||
} |
|||
} |
|||
}) |
|||
} |
|||
fn to_string(num: &Integer) -> String { |
|||
let str = num.to_string(); |
|||
let len = str.len(); |
|||
if len > 40 { |
|||
let mut result = String::from(&str[..20]); |
|||
result.push_str("..."); |
|||
result.push_str(&str[len - 20..]); |
|||
result.push_str(" ("); |
|||
result.push_str(&len.to_string()); |
|||
result.push_str(" digits)"); |
|||
return result; |
|||
} |
|||
str |
|||
} |
|||
fn main() { |
|||
use std::time::Instant; |
|||
let now = Instant::now(); |
|||
for (i, (n, f)) in prime_fibonacci().take(26).enumerate() { |
|||
println!("{}: F({}) = {}", i + 1, n, to_string(&f)); |
|||
} |
|||
let time = now.elapsed(); |
|||
println!("elapsed time: {} milliseconds", time.as_millis()); |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
1: F(3) = 2 |
|||
2: F(4) = 3 |
|||
3: F(5) = 5 |
|||
4: F(7) = 13 |
|||
5: F(11) = 89 |
|||
6: F(13) = 233 |
|||
7: F(17) = 1597 |
|||
8: F(23) = 28657 |
|||
9: F(29) = 514229 |
|||
10: F(43) = 433494437 |
|||
11: F(47) = 2971215073 |
|||
12: F(83) = 99194853094755497 |
|||
13: F(131) = 1066340417491710595814572169 |
|||
14: F(137) = 19134702400093278081449423917 |
|||
15: F(359) = 47542043773469822074...62268716376935476241 (75 digits) |
|||
16: F(431) = 52989271100609562179...55134424689676262369 (90 digits) |
|||
17: F(433) = 13872771278047838271...25954602593712568353 (91 digits) |
|||
18: F(449) = 30617199924845450305...49015933442805665949 (94 digits) |
|||
19: F(509) = 10597999265301490732...54396195769876129909 (107 digits) |
|||
20: F(569) = 36684474316080978061...15228143777781065869 (119 digits) |
|||
21: F(571) = 96041200618922553823...31637646183008074629 (119 digits) |
|||
22: F(2971) = 35710356064190986072...48642001438470316229 (621 digits) |
|||
23: F(4723) = 50019563612695729290...02854387700053591957 (987 digits) |
|||
24: F(5387) = 29304412869392580554...82040327194725855833 (1126 digits) |
|||
25: F(9311) = 34232086066590238613...37580645424669476289 (1946 digits) |
|||
26: F(9677) = 10565977873308861656...95169792504550670357 (2023 digits) |
|||
elapsed time: 22642 milliseconds |
|||
</pre> |
</pre> |
||