46 lines
1 KiB
Text
46 lines
1 KiB
Text
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_curzon(n: usize, k: usize) -> bool {
|
|
let m = k * n + 1;
|
|
modpow(k, n, m) + 1 == m
|
|
|
|
}
|
|
|
|
fn main() {
|
|
for k in (2..=10).step_by(2) {
|
|
println!("Curzon numbers with base {k}:");
|
|
let mut count = 0;
|
|
let mut n = 1;
|
|
while count < 50 {
|
|
if is_curzon(n, k) {
|
|
count += 1;
|
|
print!("{:4}{}", n, if count % 10 == 0 { "\n" } else { " " });
|
|
}
|
|
n += 1;
|
|
}
|
|
loop {
|
|
if is_curzon(n, k) {
|
|
count += 1;
|
|
if count == 1000 {
|
|
break;
|
|
}
|
|
}
|
|
n += 1;
|
|
}
|
|
println!("1000th Curzon number with base {k}: {n}\n");
|
|
}
|
|
}
|