Partition an integer x into n primes: Difference between revisions
m
Separated Rust code into modules
m (→{{header|Haskell}}: Tidying) |
m (Separated Rust code into modules) |
||
Line 1,764:
=={{header|Rust}}==
{{trans|C}}
<lang rust>
mod bit_array;
mod prime_sieve;
use prime_sieve::PrimeSieve;
fn find_prime_partition(
number: usize,
count: usize,
min_prime: usize,
index: usize,
) -> bool {
if count == 1 {
if number >= min_prime && sieve.is_prime(number) {
Line 1,828 ⟶ 1,786:
}
for p in min_prime..number {
if sieve.is_prime(p)
&& find_prime_partition(sieve, number - p, count - 1, p + 1, primes, index + 1)
{
primes[index] = p;
return true;
Line 1,837 ⟶ 1,796:
}
fn print_prime_partition(sieve
let mut primes = vec![0; count];
if !find_prime_partition(sieve, number, count, 2, &mut primes, 0) {
Line 1,862 ⟶ 1,821:
print_prime_partition(&s, 22699, 4);
print_prime_partition(&s, 40355, 3);
}</lang>
<lang rust>// prime_sieve.rs
use crate::bit_array;
pub struct PrimeSieve {
composite: bit_array::BitArray,
}
impl PrimeSieve {
pub fn new(limit: usize) -> PrimeSieve {
let mut sieve = PrimeSieve {
composite: bit_array::BitArray::new(limit / 2),
};
let mut p = 3;
while p * p <= limit {
if !sieve.composite.get(p / 2 - 1) {
let inc = p * 2;
let mut q = p * p;
while q <= limit {
sieve.composite.set(q / 2 - 1, true);
q += inc;
}
}
p += 2;
}
sieve
}
pub fn is_prime(&self, n: usize) -> bool {
if n < 2 {
return false;
}
if n % 2 == 0 {
return n == 2;
}
!self.composite.get(n / 2 - 1)
}
}</lang>
<lang rust>// bit_array.rs
pub struct BitArray {
array: Vec<u32>,
}
impl BitArray {
pub fn new(size: usize) -> BitArray {
BitArray {
array: vec![0; (size + 31) / 32],
}
}
pub fn get(&self, index: usize) -> bool {
let bit = 1 << (index & 31);
(self.array[index >> 5] & bit) != 0
}
pub fn set(&mut self, index: usize, new_val: bool) {
let bit = 1 << (index & 31);
if new_val {
self.array[index >> 5] |= bit;
} else {
self.array[index >> 5] &= !bit;
}
}
}</lang>
| |||