Partition an integer x into n primes: Difference between revisions
Content added Content deleted
m (→{{header|REXX}}: split some DO-END statements, added/changed commands and whitespace, simplified a pluralizer.) |
(Added Rust Solution) |
||
Line 1,757: | Line 1,757: | ||
Partitioned 22699 with 4 primes: 2 + 3 + 43 + 22651 |
Partitioned 22699 with 4 primes: 2 + 3 + 43 + 22651 |
||
Partitioned 40355 with 3 primes: 3 + 139 + 40213 |
Partitioned 40355 with 3 primes: 3 + 139 + 40213 |
||
</pre> |
|||
=={{header|Rust}}== |
|||
{{trans|C}} |
|||
<lang rust>struct BitArray { |
|||
array : Vec<u32> |
|||
} |
|||
impl BitArray { |
|||
fn new(size : usize) -> BitArray { |
|||
BitArray { array : vec![0; (size+31)/32] } |
|||
} |
|||
fn get(&self, index : usize) -> bool { |
|||
let bit = 1 << (index & 31); |
|||
(self.array[index >> 5] & bit) != 0 |
|||
} |
|||
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; |
|||
} |
|||
} |
|||
} |
|||
struct PrimeSieve { |
|||
composite : BitArray |
|||
} |
|||
impl PrimeSieve { |
|||
fn new(limit : usize) -> PrimeSieve { |
|||
let mut sieve = PrimeSieve { composite : 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 |
|||
} |
|||
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) |
|||
} |
|||
} |
|||
fn find_prime_partition(sieve : &PrimeSieve, number : usize, count : usize, |
|||
min_prime : usize, primes : &mut Vec<usize>, index : usize) -> bool { |
|||
if count == 1 { |
|||
if number >= min_prime && sieve.is_prime(number) { |
|||
primes[index] = number; |
|||
return true; |
|||
} |
|||
return false; |
|||
} |
|||
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; |
|||
} |
|||
} |
|||
false |
|||
} |
|||
fn print_prime_partition(sieve : &PrimeSieve, number : usize, count : usize) { |
|||
let mut primes = vec![0; count]; |
|||
if !find_prime_partition(sieve, number, count, 2, &mut primes, 0) { |
|||
println!("{} cannot be partitioned into {} primes.", number, count); |
|||
} else { |
|||
print!("{} = {}", number, primes[0]); |
|||
for i in 1..count { |
|||
print!(" + {}", primes[i]); |
|||
} |
|||
println!(); |
|||
} |
|||
} |
|||
fn main() { |
|||
let s = PrimeSieve::new(100000); |
|||
print_prime_partition(&s, 99809, 1); |
|||
print_prime_partition(&s, 18, 2); |
|||
print_prime_partition(&s, 19, 3); |
|||
print_prime_partition(&s, 20, 4); |
|||
print_prime_partition(&s, 2017, 24); |
|||
print_prime_partition(&s, 22699, 1); |
|||
print_prime_partition(&s, 22699, 2); |
|||
print_prime_partition(&s, 22699, 3); |
|||
print_prime_partition(&s, 22699, 4); |
|||
print_prime_partition(&s, 40355, 3); |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
99809 = 99809 |
|||
18 = 5 + 13 |
|||
19 = 3 + 5 + 11 |
|||
20 cannot be partitioned into 4 primes. |
|||
2017 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 + 59 + 61 + 67 + 71 + 73 + 79 + 97 + 1129 |
|||
22699 = 22699 |
|||
22699 = 2 + 22697 |
|||
22699 = 3 + 5 + 22691 |
|||
22699 = 2 + 3 + 43 + 22651 |
|||
40355 = 3 + 139 + 40213 |
|||
</pre> |
</pre> |
||