Unprimeable numbers: Difference between revisions
Content added Content deleted
m (C++ - renamed class) |
m (Separated Rust code into modules) |
||
| Line 1,963: | Line 1,963: | ||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
<lang rust> |
<lang rust>// main.rs |
||
mod bit_array; |
|||
array : Vec<u32> |
|||
mod prime_sieve; |
|||
} |
|||
use prime_sieve::PrimeSieve; |
|||
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) |
|||
} |
|||
} |
|||
// return number of decimal digits |
// return number of decimal digits |
||
| Line 2,037: | Line 1,989: | ||
index -= 1; |
index -= 1; |
||
} |
} |
||
changed += (10 * (n/10) + new_digit) * p; |
changed += (10 * (n / 10) + new_digit) * p; |
||
changed |
changed |
||
} |
} |
||
| Line 2,085: | Line 2,037: | ||
} |
} |
||
for i in 0..10 { |
for i in 0..10 { |
||
println!("Least unprimeable number ending in {}: {}" |
println!("Least unprimeable number ending in {}: {}", i, lowest[i]); |
||
} |
|||
}</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> |
}</lang> |
||