94 lines
2.2 KiB
Text
94 lines
2.2 KiB
Text
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 find_primes(from: u32, to: u32) -> Vec<u32> {
|
|
let mut primes: Vec<u32> = Vec::new();
|
|
for p in from..=to {
|
|
if is_prime(p) {
|
|
primes.push(p);
|
|
}
|
|
}
|
|
primes
|
|
}
|
|
|
|
fn find_nsmooth_numbers(n: u32, count: usize) -> Vec<u128> {
|
|
let primes = find_primes(2, n);
|
|
let num_primes = primes.len();
|
|
let mut result = Vec::with_capacity(count);
|
|
let mut queue = Vec::with_capacity(num_primes);
|
|
let mut index = Vec::with_capacity(num_primes);
|
|
for i in 0..num_primes {
|
|
index.push(0);
|
|
queue.push(primes[i] as u128);
|
|
}
|
|
result.push(1);
|
|
for i in 1..count {
|
|
for p in 0..num_primes {
|
|
if queue[p] == result[i - 1] {
|
|
index[p] += 1;
|
|
queue[p] = result[index[p]] * primes[p] as u128;
|
|
}
|
|
}
|
|
let mut min_index: usize = 0;
|
|
for p in 1..num_primes {
|
|
if queue[min_index] > queue[p] {
|
|
min_index = p;
|
|
}
|
|
}
|
|
result.push(queue[min_index]);
|
|
}
|
|
result
|
|
}
|
|
|
|
fn print_nsmooth_numbers(n: u32, begin: usize, count: usize) {
|
|
let numbers = find_nsmooth_numbers(n, begin + count);
|
|
print!("{}: {}", n, &numbers[begin]);
|
|
for i in 1..count {
|
|
print!(", {}", &numbers[begin + i]);
|
|
}
|
|
println!();
|
|
}
|
|
|
|
fn main() {
|
|
println!("First 25 n-smooth numbers for n = 2 -> 29:");
|
|
for n in 2..=29 {
|
|
if is_prime(n) {
|
|
print_nsmooth_numbers(n, 0, 25);
|
|
}
|
|
}
|
|
println!();
|
|
println!("3 n-smooth numbers starting from 3000th for n = 3 -> 29:");
|
|
for n in 3..=29 {
|
|
if is_prime(n) {
|
|
print_nsmooth_numbers(n, 2999, 3);
|
|
}
|
|
}
|
|
println!();
|
|
println!("20 n-smooth numbers starting from 30,000th for n = 503 -> 521:");
|
|
for n in 503..=521 {
|
|
if is_prime(n) {
|
|
print_nsmooth_numbers(n, 29999, 20);
|
|
}
|
|
}
|
|
}
|