107 lines
2.2 KiB
Plaintext
107 lines
2.2 KiB
Plaintext
// [dependencies]
|
|
// rug = "1.8"
|
|
|
|
fn is_prime(n: u32) -> bool {
|
|
if n < 2 {
|
|
return false;
|
|
}
|
|
if n % 2 == 0 {
|
|
return n == 2;
|
|
}
|
|
if n % 3 == 0 {
|
|
return n == 3;
|
|
}
|
|
let mut p = 5;
|
|
while p * p <= n {
|
|
if n % p == 0 {
|
|
return false;
|
|
}
|
|
p += 2;
|
|
if n % p == 0 {
|
|
return false;
|
|
}
|
|
p += 4;
|
|
}
|
|
true
|
|
}
|
|
|
|
fn cycle(n: u32) -> u32 {
|
|
let mut m: u32 = n;
|
|
let mut p: u32 = 1;
|
|
while m >= 10 {
|
|
p *= 10;
|
|
m /= 10;
|
|
}
|
|
m + 10 * (n % p)
|
|
}
|
|
|
|
fn is_circular_prime(p: u32) -> bool {
|
|
if !is_prime(p) {
|
|
return false;
|
|
}
|
|
let mut p2: u32 = cycle(p);
|
|
while p2 != p {
|
|
if p2 < p || !is_prime(p2) {
|
|
return false;
|
|
}
|
|
p2 = cycle(p2);
|
|
}
|
|
true
|
|
}
|
|
|
|
fn test_repunit(digits: usize) {
|
|
use rug::{integer::IsPrime, Integer};
|
|
let repunit = "1".repeat(digits);
|
|
let bignum = Integer::from_str_radix(&repunit, 10).unwrap();
|
|
if bignum.is_probably_prime(10) != IsPrime::No {
|
|
println!("R({}) is probably prime.", digits);
|
|
} else {
|
|
println!("R({}) is not prime.", digits);
|
|
}
|
|
}
|
|
|
|
fn main() {
|
|
use rug::{integer::IsPrime, Integer};
|
|
println!("First 19 circular primes:");
|
|
let mut count = 0;
|
|
let mut p: u32 = 2;
|
|
while count < 19 {
|
|
if is_circular_prime(p) {
|
|
if count > 0 {
|
|
print!(", ");
|
|
}
|
|
print!("{}", p);
|
|
count += 1;
|
|
}
|
|
p += 1;
|
|
}
|
|
println!();
|
|
println!("Next 4 circular primes:");
|
|
let mut repunit: u32 = 1;
|
|
let mut digits: usize = 1;
|
|
while repunit < p {
|
|
repunit = 10 * repunit + 1;
|
|
digits += 1;
|
|
}
|
|
let mut bignum = Integer::from(repunit);
|
|
count = 0;
|
|
while count < 4 {
|
|
if bignum.is_probably_prime(15) != IsPrime::No {
|
|
if count > 0 {
|
|
print!(", ");
|
|
}
|
|
print!("R({})", digits);
|
|
count += 1;
|
|
}
|
|
digits += 1;
|
|
bignum = bignum * 10 + 1;
|
|
}
|
|
println!();
|
|
test_repunit(5003);
|
|
test_repunit(9887);
|
|
test_repunit(15073);
|
|
test_repunit(25031);
|
|
test_repunit(35317);
|
|
test_repunit(49081);
|
|
}
|