При вводе n я пытаюсь вывести n-е простое число. Сито Эратосфена казалось хорошим способом сделать это, но у меня возникли проблемы с размером массива, который необходимо просеять.
Я использую массив, в котором каждый член равен 1 и представляет число. Если сито отфильтровывает число, значение изменяется на 0, что означает, что число не простое. Как только он достигает n-го члена, который имеет значение 1, возвращается значение индекса.
Я пытаюсь установить разумный размер массива для любого данного n. Но у меня есть две проблемы.
Поскольку мне кажется, что мне необходимо установить размер массива на постоянное значение, я не могу найти способ использовать размер n для аппроксимацииТребуемый размер массива. Это означает, что я всегда использую массив величиной 10e6, даже когда n мало.
Этот подход основан на наличии большого массива, поскольку он использует ранние значения для изменения более поздних значений. Это означает, что при n> 10e7 мой массив перебивает стек. Есть ли способ обойти эту проблему, не переходя в кучу?
Я пытался решить первую проблему, используя const, например:
pub fn nth(n: u32) -> u32 {
const ARRAY_SIZE : usize = f(n) // where f(n) is some approximation of required array size
let mut primes: [usize; ARRAY_SIZE] = [1; ARRAY_SIZE];
...
}
Однако, это не обходит требование иметь фиксированный размер массива.
Есть предложения? Также я очень новичок в ржавчине, и любые предложения, чтобы сделать его более ржавым, приветствуются.
Ниже моя попытка, которая имеет массив фиксированного размера и работает для значений n <= 10,000: </p>
pub fn nth(n: u32) -> u32 {
// Eratosthene's Sieve Algorithm
let mut output: u32 = 0;
let mut primes: [usize; 104_827] = [1; 104_827];
primes[0] = 0;
primes[1] = 0;
let mut prime_count = 0;
for i in 2..(primes.len() as usize) {
if primes[i] == 1 {
if prime_count == n as usize { output = i as u32; }
prime_count += 1;
let mut j: usize = 2;
while i * j <= primes.len() as usize {
primes[i * j] = 0;
j += 1;
}
}
}
output
}
edit: Спасибо за отличные ответы! Я изменил функцию, чтобы использовать оценку (n * (n * n.ln()).ln()), заменил массив usize вектором bools. Жаль, что я не могу заставить более низкие значения этой работы только на стеке, потому что метод на основе массива быстрее, чем метод на основе вектора, когда размер массива близок к приближению.
Я попытался использовать ранний возврат и отказаться от output, но не мог понять, как заставить это работать. У меня есть код в конце этого редактирования с закомментированными строками, где я пытался поставить ранний возврат и unreachable!(), но он всегда паниковал. Если бы кто-то мог указать на мою ошибку, это было бы здорово.
Я собирался изменить самый внутренний цикл while в цикл for, как предложено NieDzejkob, но когда я запустил числа для скоростиwhile против for, я обнаружил, что цикл while быстрее. Кто-нибудь знает, почему это может быть?
Также у меня были некоторые проблемы с 0-9-м, 11-м и 12-м простыми числами, поэтому я просто установил приближение для работы выше этого диапазона.
100-е простое while_func = 547, for_func = 547
простое while_func 152.431 мкс против for_func 216.043 мкс
1000-е простое while_func = 7927, for_func = 7927
простое while_func 2.099213ms против for_func 3.362854th
1049= 104743, for_func = 104743
простое время while_func 28,166767 мс против for_func 44,967197мс
100000-е простое while_func = 1299721, for_func = 1299721
простое время while_func 339,324756 мс против for_func 559,755_586 = 5,66 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 = 5,600 для финн. = 15485867
prime while_func 4.151047728s против for_func 6.950281943s
pub fn nth(n: u32) -> u32 {
// Eratosthene's Sieve Algorithm
let estimate = estimate_size(n);
let mut primes: Vec<bool> = vec![true; estimate + 1];
primes[0] = false;
primes[1] = false;
let mut output: u32 = 0; // remove if unreachable!() works
let mut prime_count: u32 = 0;
for i in 2..(estimate) {
if primes[i] == true {
if prime_count == n { output = i as u32; }
// if prime_count == n { return i as u32; }
prime_count += 1;
let mut j: usize = 2;
while i * j <= estimate {
primes[i * j] = false;
j += 1;
}
// for j in (2*i ..= estimate).step_by(i) {
// primes[j] = false;
// }
}
}
output
// unreachable!()
}
fn estimate_size(n: u32) -> usize {
if n < 14 {
44 as usize
} else {
let n = n as f64;
(n * (n * n.ln()).ln()).ceil() as usize
}
}