We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #216: Investigating the primality of numbers of the form 2n² - 1
  4. Discussions

Project Euler #216: Investigating the primality of numbers of the form 2n² - 1

  • agarg536
     + 0 comments

    this is my code. I used sieve of eratosthenes to get possible primes till the Nth value. passed basic test cases but getting wrong answer in others can anyone share robust test cases or any other approach?

    #python code
import math
def getPrimeCount(N, abc):
    a = int(abc[0])
    b = int(abc[1])
    c = int(abc[2])
    nth = a*(N**2) + b*N + c

    primeSieve = [True]*(nth + 1)
    primeSieve[0] = False
    primeSieve[1] = False

    count = 0
    root = math.floor(math.sqrt(nth))
    i=2
    while i<= root:
        if primeSieve[i] == True:
            for j in range(i*i, nth+1, i):
                primeSieve[j] = False
        i += 1
    
    for itr in range(N+1):
        val = a*(itr**2) + b*itr + c
        if val > 1 and primeSieve[val]:
            count += 1

    return count

abc = input().split()
queries = int(input())
for _ in range(queries):
    n = int(input())
    print(getPrimeCount(n, abc))