Первая - прямой перебор, но хорошо оптимизированный: с целочисленным вычислением корня для короткой схемы на квадратах. У меня на компьютере работает впритык, за 2.8 для 100k. Если бы не питон - укладывалось бы, но лень переписывать. На тестовом сервере скорее всего не уложится в таймлимит, просто для информации, что так тоже можно:
def prime_count(N):
primes = [2, 3]
i, s, s2 = 5, 3, 9
while len(primes) < N:
while s2 <= i:
s += 1
s2 = s*s
flag = True
for p in primes:
if p > s+1:
break
if i % p == 0:
flag = False
break
if flag:
primes.append(i)
i += 2
return primes[N-1]
print(prime_count(int(input(
Вторая: обычное решето Эратосфена. Сравни, насколько короче получилось =) Число 13 выведено эмпирически, для K<=100000 оно подходит, но потом будет маленьким. В общем случае там должна стоять величина log2(N) с каким-то множителем по теореме о плотности простых чисел. Для 100k работает раз в 15 быстрее, так что в лимит уложится точно:
def eratosthenes(N):
i, numbers = 0, [True] * (13 * N)
for index in range(N):
while not numbers[i]: i += 1
numbers[i::i+2] = [False] * len(numbers[i::i+2])
return i+2
print(eratosthenes(int(input(
(см. объяснение)
Объяснение:
Решим задачу с Python 3:
k = 0
for x1 in range(2):
for x2 in range(2):
for x3 in range(2):
for x4 in range(2):
for x5 in range(2):
for x6 in range(2):
for x7 in range(2):
for x8 in range(2):
for x9 in range(2):
for x10 in range(2):
if (((x1 == x2) and (x3 == x4)) or (
not (x1 == x2) and not (x3 == x4)) == 0) and (
((x3 == x4) and (x5 == x6)) or (
not (x3 == x4) and not (x5 == x6)) == 0) and (
((x5 == x6) and (x7 == x8)) or (
not (x5 == x6) and not (x7 == x8)) == 0) and (
((x7 == x8) and (x9 == x10)) or (
not (x7 == x8) and not (x9 == x10)) == 0):
k += 1
print(k)
Результат работы программы: 416.
Задание выполнено!
Объяснение:
(61+168)-2(72:(2+15))=220