78 lines
1.7 KiB
Plaintext
78 lines
1.7 KiB
Plaintext
// main.rs
|
|
// References:
|
|
// https://en.wikipedia.org/wiki/Full_reptend_prime
|
|
// https://en.wikipedia.org/wiki/Primitive_root_modulo_n#Finding_primitive_roots
|
|
|
|
mod bit_array;
|
|
mod prime_sieve;
|
|
|
|
use prime_sieve::PrimeSieve;
|
|
|
|
fn modpow(mut base: usize, mut exp: usize, n: usize) -> usize {
|
|
if n == 1 {
|
|
return 0;
|
|
}
|
|
let mut result = 1;
|
|
base %= n;
|
|
while exp > 0 {
|
|
if (exp & 1) == 1 {
|
|
result = (result * base) % n;
|
|
}
|
|
base = (base * base) % n;
|
|
exp >>= 1;
|
|
}
|
|
result
|
|
}
|
|
|
|
fn is_long_prime(sieve: &PrimeSieve, prime: usize) -> bool {
|
|
if !sieve.is_prime(prime) {
|
|
return false;
|
|
}
|
|
if 10 % prime == 0 {
|
|
return false;
|
|
}
|
|
let n = prime - 1;
|
|
let mut m = n;
|
|
let mut p = 2;
|
|
while p * p <= n {
|
|
if sieve.is_prime(p) && m % p == 0 {
|
|
if modpow(10, n / p, prime) == 1 {
|
|
return false;
|
|
}
|
|
while m % p == 0 {
|
|
m /= p;
|
|
}
|
|
}
|
|
p += 1;
|
|
}
|
|
if m == 1 {
|
|
return true;
|
|
}
|
|
modpow(10, n / m, prime) != 1
|
|
}
|
|
|
|
fn long_primes(limit1: usize, limit2: usize) {
|
|
let sieve = PrimeSieve::new(limit2);
|
|
let mut count = 0;
|
|
let mut limit = limit1;
|
|
let mut prime = 3;
|
|
while prime < limit2 {
|
|
if is_long_prime(&sieve, prime) {
|
|
if prime < limit1 {
|
|
print!("{} ", prime);
|
|
}
|
|
if prime > limit {
|
|
print!("\nNumber of long primes up to {}: {}", limit, count);
|
|
limit *= 2;
|
|
}
|
|
count += 1;
|
|
}
|
|
prime += 2;
|
|
}
|
|
println!("\nNumber of long primes up to {}: {}", limit, count);
|
|
}
|
|
|
|
fn main() {
|
|
long_primes(500, 8192000);
|
|
}
|