Простое число — это целое число больше 1, которое делится только на 1 и само на себя. Сложите все простые числа, строго меньшие limit. Сам limit не включается в сумму, даже если он простое число.
Реализуйте функцию prime_sum(limit).
Входные данные
limit: Верхняя граница (не включительно).
Выходные данные
Верните сумму подходящих простых чисел, либо 0, если таких чисел нет.
Ограничения
0 ≤ limit ≤ 2,000,000. Возвращайте сумму в виде знакового 64-битного целого числа.
Примеры
Ввод:
limit = 12
Ожидаемый вывод:
expected = 28Ввод:
long long limit = 12;
Ожидаемый вывод:
long long expected = 28;Ввод:
long limit = 12;
Ожидаемый вывод:
long expected = 28;Пояснение
Простые числа меньше 12: 2, 3, 5, 7 и 11; их сумма равна 28.
Ввод:
limit = 2
Ожидаемый вывод:
expected = 0Ввод:
long long limit = 2;
Ожидаемый вывод:
long long expected = 0;Ввод:
long limit = 2;
Ожидаемый вывод:
long expected = 0;Пояснение
Нет простых чисел строго меньше 2.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Основная цена — эффективный поиск простых; наивная проверка делимости для каждого числа будет слишком медленной.
Подсказка 2
Используйте подход, похожий на решето, чтобы пометить составные, затем сложите числа, которые остались непомеченными и меньше limit.
Подсказка 3
Помните, что сам limit не включается, даже если он прост, а маленькие limit могут не дать ничего.
Ожидаемая сложность
время O(limit log log limit), доп. память O(limit)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.