Условие:
Оружейник Просперо и гимнаст Тибул подняли народ против режима Трех Толстяков, и повели людей, чтобы взять штурмом их дворец. Однако гвардейцам удалось подавить бунт, оружейник Просперо был арестован и заключен в тюрьму. Тибул же успел спастись бегством. Теперь гимнаст обдумывает как ему спасти товарища. На камере, в которой сидит Просперо установлен кодовый замок. Код определяется тремя числами, каждое из которых может быть в пределах от 1 до n. Суок удалось узнать, что в правильном коде сумма этих трех чисел является простым числом. Естественно, этой информации может оказаться недостаточно для того, чтобы точно знать код, но может значительно сократить перебор.
Напишите программу, определяющую количество комбинаций, которые нужно перебрать Тибулу, когда он проникнет в тюрьму.
Задача:
Входные данные:
Целое число n (1 ≤ n ≤ 10000).
Выходные данные:
Выведите количество комбинаций из трех чисел от 1 до n таких, что сумма чисел является простым числом.
Пример:
| Ввод #1 | Вывод #1 |
|---|---|
| 3 | 13 |
Ограничения:
- Ограничение по времени выполнения: 1 секунда
- Ограничение по использованию памяти: 64 мегабайта
Gemini 2.0 thinking решить задачу не смог, при n=10000 IDE python зависает намертво, но deepseek решил доступным способом. Пожалуйста сделайте чтобы Gemini 2.0 thinking смог также решать такие задачи!
deepseek решил задачу
if k < 2:
return 0
return k * (k - 1) // 2
def sieve(limit):
is_prime = [True] * (limit + 1)
is_prime[0] = is_prime[1] = False
for current in range(2, int(limit**0.5) + 1):
if is_prime[current]:
for multiple in range(current*current, limit + 1, current):
is_prime[multiple] = False
return is_prime
def main():
n = int(input())
max_p = 3 * n
is_prime = sieve(max_p)
total = 0
for p in range(3, max_p + 1):
if is_prime[p]:
term1 = comb(p - 1)
term2 = 3 * comb(p - n - 1)
term3 = 3 * comb(p - 2 * n - 1)
term4 = comb(p - 3 * n - 1)
total += term1 - term2 + term3 - term4
print(total)
if __name__ == "__main__":
main()```
