This problem didn’t feel too tough to me. If anything, the hardest part was
figuring out how many primes I needed to produce. Ends up I need two more than
the square root of n. Other than that, this problem felt pretty
straightforward.
def solve(n):
def is_prime(n):
stop = n ** 0.5
for p in primes:
if n % p == 0:
return False
if p > stop:
return True
return True
top = int(n ** 0.5)
sieve = [False, False] + [True] * (top - 1)
primes = []
for p, isprime in enumerate(sieve):
if not isprime:
continue
primes.append(p)
num = p + p
while num <= top:
sieve[num] = False
num += p
added = False
while True:
p += 1
if is_prime(p):
primes.append(p)
if added:
break
added = True
lps = primes.pop(0)
ups = primes.pop(0)
total = 0
while primes:
num = lps**2 + lps
while num < min(n, ups**2):
if num % ups != 0:
total += num
num += lps
num = ups**2 - ups
while num > n:
num -= ups
while num > lps**2:
if num % lps != 0:
total += num
num -= ups
lps, ups = ups, primes.pop(0)
if lps**2 > n:
break
return total
if __name__ == '__main__':
import sys
n = eval(sys.argv[1])
print(solve(n))
import pytest
from problem import solve
_test_solve = (
(15, 30),
(10**1, 18),
(10**2, 1068),
(10**3, 34825),
(10**4, 1134942),
(10**5, 36393008),
(10**6, 1187195869),
(10**7, 38220347691),
(10**8, 1220691369414),
(10**9, 39031016614640),
)
@pytest.mark.parametrize('n,expect', _test_solve)
def test_solve(n, expect):
assert expect == solve(n)