Sieve
Sieve algorithms find all prime numbers below a specified integer. Additionally, they efficiently compute values of multiplicative functions for all integers up to that specified limit.
Finding primes
sieve
returns a vector containing all prime numbers that are less than or equal to max_val
.
This function runs with a time complexity of \(O(N)\) where \(N\) is the value of max_val
. This efficiency is achieved with linear sieve.
This function is further optimized by excluding multiples of \(2\) and \(3\) in advance.
fn sieve(max_val: usize) -> Vec<usize> {
let mut primes = vec![2, 3];
let mut is_prime = vec![true; max_val / 3 + 1];
for i in 0..is_prime.len() {
let j = 6 * (i >> 1) + 5 + ((i & 1) << 1);
if is_prime[i] {
primes.push(j);
}
for &p in primes[2..].iter() {
let v = j * p;
if v > max_val {
break;
}
is_prime[v / 3 - 1] = false;
if j % p == 0 {
break;
}
}
}
primes
}
With Euler Phi Function
fn phi_sieve(max_val: usize) -> (Vec<bool>, Vec<usize>, Vec<usize>) {
let mut primes = vec![];
let mut is_prime = vec![true; max_val + 1];
is_prime[0] = false;
is_prime[1] = false;
let mut phi = vec![0; max_val + 1];
for i in 2..=max_val {
if is_prime[i] {
primes.push(i);
phi[i] = i - 1;
}
for &p in primes.iter() {
let v = i * p;
if v > max_val {
break;
}
is_prime[v] = false;
if i % p == 0 {
phi[v] = phi[i] * p;
break;
} else {
phi[v] = phi[i] * phi[p]
}
}
}
(is_prime, phi, primes)
}
With Möbius Function
fn mobius_sieve(max_val: usize) -> (Vec<i8>, Vec<usize>) {
let mut primes = vec![];
let mut mu = vec![2i8; max_val + 1];
(mu[0], mu[1]) = (0, 1);
for i in 2..=max_val {
if mu[i] == 2 {
primes.push(i);
mu[i] = -1;
}
for &p in primes.iter() {
let v = i * p;
if v > max_val {
break;
}
if i % p == 0 {
mu[v] = 0;
break;
} else {
mu[v] = -mu[i];
}
}
}
(mu, primes)
}
Last modified on 231203.