use std::f64;
/*
Check whether a number is prime.
Uses a √n loop and skips even numbers after 2.
*/
fn is_prime(value: u32) -> bool {
if value < 2 {
return false;
}
if value == 2 {
return true;
}
if value % 2 == 0 {
return false;
}
let limit = (value as f64).sqrt() as u32;
let mut d = 3;
while d <= limit {
if value % d == 0 {
return false;
}
d += 2;
}
true
}
/*
Generate all primes up to N.
Any consecutive prime sum equal to N cannot contain primes larger than N.
*/
fn generate_primes(max_n: u32) -> Vec<u32> {
let mut primes = Vec::new();
for n in 2..=max_n {
if is_prime(n) {
primes.push(n);
}
}
primes
}
/*
Find all consecutive prime sequences whose sum equals N.
Uses a sliding window:
- Expand the window by moving the right pointer
- Shrink the window by moving the left pointer
*/
fn find_prime_consecutive_sums(n: u32) {
let primes = generate_primes(n);
let mut start: usize = 0;
let mut end: usize = 0;
let mut sum: u32 = 0;
loop {
if sum < n {
if end == primes.len() {
break;
}
sum += primes[end];
end += 1;
} else if sum > n {
sum -= primes[start];
start += 1;
} else {
// Found a valid sequence
print!("Sequence: ");
for p in &primes[start..end] {
print!("{} ", p);
}
println!();
// Continue searching
sum -= primes[start];
start += 1;
}
}
}
/*
main
*/
fn main() {
let n: u32 = 41;
println!("Consecutive prime sequences whose sum equals {}:", n);
find_prime_consecutive_sums(n);
}
/*
run:
Consecutive prime sequences whose sum equals 41:
Sequence: 2 3 5 7 11 13
Sequence: 11 13 17
Sequence: 41
*/
