Проблема ограничения памяти сита Эратосфена
В настоящее время я пытаюсь реализовать версию сита Эратосфена для проблемы Каттиса, однако я сталкиваюсь с некоторыми ограничениями памяти, которые моя реализация не пройдет.
Вот ссылка на постановку задачи . Короче говоря, проблема требует, чтобы я сначала вернул количество простых чисел, меньшее или равное n , а затем решаю для определенного количества запросов, является ли число i простым или нет. Существует ограничение на использование памяти 50 МБ, а также использование только стандартных библиотек python (нет numpy et c). Ограничение памяти - вот где я застрял.
Вот мой код:
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()
Я сделал некоторые улучшения, например, сохранил только список всех нечетных чисел, которые вдвое уменьшает использование памяти. Я также уверен, что при вычислении простых чисел код работает так, как задумано (без неправильного ответа). У меня вопрос: как сделать мой код еще более эффективным с точки зрения памяти? Стоит ли использовать другие структуры данных? Заменить мой список целых чисел логическими? Bitarray?
Любые советы очень ценны!
EDIT
После некоторой настройки кода в 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 (используя только стандартную библиотеку).
Если кто-то наткнется на аккуратный реализация проблемы в python с использованием сегментированного сита, битового массива или чего-то еще, мне было бы интересно увидеть решение.