First 9 prime Fibonacci number: Difference between revisions
Added C++, Java and Rust solutions
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:
The first 12 prime Fibonacci numbers are:
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>
Line 641 ⟶ 750:
28657
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>
Line 826 ⟶ 1,029:
2 3 5 13 89 233 1597 28657 514229
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>
| |||