61 lines
1.4 KiB
Text
61 lines
1.4 KiB
Text
fn square_free(mut n: usize) -> bool {
|
|
if n & 3 == 0 {
|
|
return false;
|
|
}
|
|
let mut p: usize = 3;
|
|
while p * p <= n {
|
|
let mut count = 0;
|
|
while n % p == 0 {
|
|
count += 1;
|
|
if count > 1 {
|
|
return false;
|
|
}
|
|
n /= p;
|
|
}
|
|
p += 2;
|
|
}
|
|
true
|
|
}
|
|
|
|
fn print_square_free_numbers(from: usize, to: usize) {
|
|
println!("Square-free numbers between {} and {}:", from, to);
|
|
let mut line = String::new();
|
|
for i in from..=to {
|
|
if square_free(i) {
|
|
if !line.is_empty() {
|
|
line.push_str(" ");
|
|
}
|
|
line.push_str(&i.to_string());
|
|
if line.len() >= 80 {
|
|
println!("{}", line);
|
|
line.clear();
|
|
}
|
|
}
|
|
}
|
|
if !line.is_empty() {
|
|
println!("{}", line);
|
|
}
|
|
}
|
|
|
|
fn print_square_free_count(from: usize, to: usize) {
|
|
let mut count = 0;
|
|
for i in from..=to {
|
|
if square_free(i) {
|
|
count += 1;
|
|
}
|
|
}
|
|
println!(
|
|
"Number of square-free numbers between {} and {}: {}",
|
|
from, to, count
|
|
)
|
|
}
|
|
|
|
fn main() {
|
|
print_square_free_numbers(1, 145);
|
|
print_square_free_numbers(1000000000000, 1000000000145);
|
|
let mut n: usize = 100;
|
|
while n <= 1000000 {
|
|
print_square_free_count(1, n);
|
|
n *= 10;
|
|
}
|
|
}
|