@calcium

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

Необходимо реализовать алгоритм, который будет считать количество простых чисел в выданном массиве. Ограничение по памяти 256 Мб, по времени 1 секунда.
Формат ввода
  • В первой строке содержится единственное число 1 ≤ n ≤ 1000 - размер выборки
  • Во второй строке содержится n целых чисел 2 ≤ ai ≤ 1012 - выборка

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

Проблема в верхнем пределе возможного числа в выборке, когда оно действительно приближается к 12 нулям выпадают исключения типа MemoryError, а если решить и эту проблему, то алгоритм не укладывается в необходимую 1 секунду.
Пытался использовать решето Эратосфена в различных реализациях, но ничего не вышло. Подозреваю, что возможно решить с помощью генераторов, но моих скиллов пока не хватает.
  • Вопрос задан
  • 147 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Тут не нужно решето. Надо просто отдельно проверить каждое число на простоту.

Подсказка: Если число не простое, то у него есть простой делитель не больше корня (потому что иначе - есть хотя бы 2 делителя и они оба больше корня и их произведение уже больше самого числа).
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
@dmshar
Непонятно, откуда у вас MemoryError. Если исходная выборка размещена в памяти, и ей хватило там места, то на что у вас расходуется память? Вам ведь не надо запоминать все полученные простые числа. Вы берете их по одному и просто выясняете - простое оно или нет.
Вот со временем - да, если у вас действительно большие числа и их к тому-же много - ну тогда переборный алгоритм быстрый не будет. Поэтому ограничение в 1 сек. - это просто какая-то мягко говоря странность, если не указывать, а какие именно числа в вашей последовательности. Для 1000 чисел, всех лежащих в диапазоне от 0 до 1001 - это одно, а для лежащих в диапазоне от 10**12-1000 до 10**12 - это совсем разное время работы.
Ответ написан
@Akina
Сетевой и системный админ, SQL-программист.
Задача явно требует расчёта этих самых простых чисел и переиспользования списка.

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы