Решето Эратосфена проблема с ограничением памяти
В настоящее время я пытаюсь реализовать версию сита Эратосфена для задачи Каттиса, однако я сталкиваюсь с некоторыми ограничениями памяти, которые моя реализация не пройдет.
Вот ссылка на постановление о проблеме. Короче говоря, проблема требует, чтобы я сначала вернул количество простых чисел, меньшее или равное n, а затем решил для определенного количества запросов, является ли число i простым или нет. . Существует ограничение на использование памяти 50 МБ, а также использование только стандартных библиотек Python (без numpy и т. д.). Ограничение памяти - это то, где я застрял.
Вот мой код:
import sys
def sieve_of_eratosthenes(xs, n):
count = len(xs) + 1
p = 3 # start at three
index = 0
while p*p < n:
for i in range(index + p, len(xs), p):
if xs[i]:
xs[i] = 0
count -= 1
temp_index = index
for i in range(index + 1, len(xs)):
if xs[i]:
p = xs[i]
temp_index += 1
break
temp_index += 1
index = temp_index
return count
def isPrime(xs, a):
if a == 1:
return False
if a == 2:
return True
if not (a & 1):
return False
return bool(xs[(a >> 1) - 1])
def main():
n, q = map(int, sys.stdin.readline().split(' '))
odds = [num for num in range(2, n+1) if (num & 1)]
print(sieve_of_eratosthenes(odds, n))
for _ in range(q):
query = int(input())
if isPrime(odds, query):
print('1')
else:
print('0')
if __name__ == "__main__":
main()
До сих пор я сделал некоторые улучшения, например, сохранил только список всех нечетных чисел, что вдвое сокращает использование памяти. Я также уверен, что код работает должным образом при вычислении простых чисел (не получая неправильного ответа). Теперь мой вопрос: как я могу сделать свой код еще более эффективным с точки зрения памяти? Должен ли я использовать некоторые другие структуры данных? Заменить мой список целых чисел логическими значениями? Битовый массив?
Любой совет очень ценится!
РЕДАКТИРОВАТЬ
После некоторой настройки кода на python я уперся в стену, где моя реализация сегментированного сита не соответствовала требованиям к памяти.
Вместо этого я решил реализовать решение на Java, что потребовало очень мало усилий. Вот код:
public int sieveOfEratosthenes(int n){
sieve = new BitSet((n+1) / 2);
int count = (n + 1) / 2;
for (int i=3; i*i <= n; i += 2){
if (isComposite(i)) {
continue;
}
// Increment by two, skipping all even numbers
for (int c = i * i; c <= n; c += 2 * i){
if(!isComposite(c)){
setComposite(c);
count--;
}
}
}
return count;
}
public boolean isComposite(int k) {
return sieve.get((k - 3) / 2); // Since we don't keep track of even numbers
}
public void setComposite(int k) {
sieve.set((k - 3) / 2); // Since we don't keep track of even numbers
}
public boolean isPrime(int a) {
if (a < 3)
return a > 1;
if (a == 2)
return true;
if ((a & 1) == 1)
return !isComposite(a);
else
return false;
}
public void run() throws Exception{
BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
String[] line = scan.readLine().split(" ");
int n = Integer.parseInt(line[0]); int q = Integer.parseInt(line[1]);
System.out.println(sieveOfEratosthenes(n));
for (int i=0; i < q; i++){
line = scan.readLine().split(" ");
System.out.println( isPrime(Integer.parseInt(line[0])) ? '1' : '0');
}
}
Я лично не нашел способа реализовать это решение BitSet в Python (используя только стандартную библиотеку).
Если кто-нибудь наткнется на аккуратную реализацию проблемы на питоне, используя сегментированное сито, битовый массив или что-то еще, мне было бы интересно увидеть решение.
