problem 123 https projecteuler netproblem123 name prime square remainders let pn be the nth prime 2 3 5 7 11 and let r be the remainder when pn1n pn1n is divided by pn2 for example when n 3 p3 5 and 43 63 280 5 mod 25 the least value of n for which the remainder first exceeds 109 is 7037 find the least value of n for which the remainder first exceeds 1010 solution n1 p1 p1 2p n2 p12 p12 p2 1 2p p2 1 2p using pb2 p2 b2 2pb pb2 p2 b2 2pb and b 1 2p2 2 n3 p13 p13 similarly using pb3 pb3 formula and so on 2p3 6p n4 2p4 12p2 2 n5 2p5 20p3 10p as you could see when the expression is divided by p2 except for the last term the rest will result in the remainder 0 n1 2p n2 2 n3 6p n4 2 n5 10p so it could be simplified as r 2pn when n is odd r 2 when n is even returns a prime number generator using sieve method typesieve class generator primes sieve nextprimes 2 nextprimes 3 nextprimes 5 nextprimes 7 nextprimes 11 nextprimes 13 returns the least value of n for which the remainder first exceeds 1010 solution1e8 2371 solution1e9 7037 ignore the next prime as the reminder will be 2 returns a prime number generator using sieve method type sieve class generator primes sieve next primes 2 next primes 3 next primes 5 next primes 7 next primes 11 next primes 13 returns the least value of n for which the remainder first exceeds 10 10 solution 1e8 2371 solution 1e9 7037 ignore the next prime as the reminder will be 2
from __future__ import annotations

from collections.abc import Generator


def sieve() -> Generator[int, None, None]:
    
    factor_map: dict[int, int] = {}
    prime = 2
    while True:
        factor = factor_map.pop(prime, None)
        if factor:
            x = factor + prime
            while x in factor_map:
                x += factor
            factor_map[x] = factor
        else:
            factor_map[prime * prime] = prime
            yield prime
        prime += 1


def solution(limit: float = 1e10) -> int:
    
    primes = sieve()

    n = 1
    while True:
        prime = next(primes)
        if (2 * prime * n) > limit:
            return n
        
        next(primes)
        n += 2


if __name__ == "__main__":
    print(solution())