Project Euler #27: Quadratic primes

  • + 0 comments
    from sys import stdin
    
    read = stdin.readline
    
    N = int(2e3)
    
    sieve = [True] * (N + 1)
    
    sieve[0] = sieve[1] = False
    
    for p in range(2, int(N ** .5) + 1):
        if sieve[p]:
            for n in range(p * p, N + 1, p):
                sieve[n] = False
                
    n = int(read())
                
    res, res_a, res_b = 0, 0, 0
                
    def find(a, b):
        count = 0
        for n0 in range(n):
            maybe = n0**2 + n0*a + b
            if maybe > N or maybe < 2 or not sieve[maybe]:
                break
            count += 1
        return count
    
    for b in range(2, n + 1):
        if not sieve[b]:
            continue
        for a in range(-n, n + 1):
            x = find(a, b)
            if x > res:
                res = x
                res_a, res_b = a, b
            
    print(res_a, res_b)