Как найти количество простых чисел в массиве?

Question

[calcium]

Необходимо реализовать алгоритм, который будет считать количество простых чисел в выданном массиве. Ограничение по памяти 256 Мб, по времени 1 секунда.
Формат ввода

• В первой строке содержится единственное число 1 ≤ n ≤ 1000 - размер выборки
  
• Во второй строке содержится n целых чисел 2 ≤ a_i ≤ 10¹² - выборка
  

Sample Input 3:
5
15 17 2 8 15
Sample Output 3:
2

Проблема в верхнем пределе возможного числа в выборке, когда оно действительно приближается к 12 нулям выпадают исключения типа MemoryError, а если решить и эту проблему, то алгоритм не укладывается в необходимую 1 секунду.
Пытался использовать решето Эратосфена в различных реализациях, но ничего не вышло. Подозреваю, что возможно решить с помощью генераторов, но моих скиллов пока не хватает.

Comments

[Дмитрий Темников]

s=0
for elem in input().split(" "):
   if isprimary(elem): 
      s=s+1

Answer 1

[Wataru]

Тут не нужно решето. Надо просто отдельно проверить каждое число на простоту.

Подсказка: Если число не простое, то у него есть простой делитель не больше корня (потому что иначе - есть хотя бы 2 делителя и они оба больше корня и их произведение уже больше самого числа).

Comments

[calcium]

Спасибо, буду пробовать! :)

Answer 2

[dmshar]

Непонятно, откуда у вас MemoryError. Если исходная выборка размещена в памяти, и ей хватило там места, то на что у вас расходуется память? Вам ведь не надо запоминать все полученные простые числа. Вы берете их по одному и просто выясняете - простое оно или нет.
Вот со временем - да, если у вас действительно большие числа и их к тому-же много - ну тогда переборный алгоритм быстрый не будет. Поэтому ограничение в 1 сек. - это просто какая-то мягко говоря странность, если не указывать, а какие именно числа в вашей последовательности. Для 1000 чисел, всех лежащих в диапазоне от 0 до 1001 - это одно, а для лежащих в диапазоне от 10**12-1000 до 10**12 - это совсем разное время работы.

Comments

[Wataru]

Память, очевидно, кончилась при попытке завести массив длинной 10^12 для решета эратосфена.

А про вермя - это же ограничение. Надо уложиться в 1 сек при 1000 практически максимальных числах, что вполне реально, если правильный алгоритм использовать.

Answer 3

[Akina]

Задача явно требует расчёта этих самых простых чисел и переиспользования списка.

Так что сначала генерим список простых чисел во вменяемом диапазоне, скажем, до тысячи. Берём очередное число. Если оно меньше квадрата самого большого из простых чисел списка, проверяем, что оно делится или не делится на какое-то из них. А если больше - просто перед проверкой догенерируем в список простые числа до нужного порога. При этом используем повторно ту же самую процедуру проверки числа на простоту.

Нет, конечно, можно и сразу нагенерить простых до миллиона, но смысл?