P357_prime_generating_integers

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Thu Aug 13 12:25:30 2020

@author: manish
"""
from math import sqrt
from numba import jit

@jit
def sieve_of_erat(N):
    """
    Function implements sieve of Eratosthenes (for all numbers uptil N).
    Returns array erat_sieve
    If erat_sieve[i] is True, then 2*i + 3 is a prime.
    """
    lim = int(N/2)
    if N % 2 == 0:
        lim -= 1
    erat_sieve = [True]*lim
    prime_list = []
    prime_list.append(2)
    for i in range(int((sqrt(N)-3)/2)+1):  # Only need to run till sqrt(n)
        if erat_sieve[i] == True:
            j = i + (2*i+3)
            while j < lim:
                erat_sieve[j] = False
                j += (2*i+3)
    for i in range(lim):
        if erat_sieve[i] == True:
            prime_list.append(2*i+3)
        
    return erat_sieve, prime_list


def isprime(x, esieve):
    if x % 2 ==0:
        return False
    y = (x-3)//2
    return esieve[y]


def is_prime_gen_integer(N, esieve):
    sq_N = int(sqrt(N))
    for d in range(2, sq_N + 1):
        if N % d == 0:
            x = N // d + d
            if x % 2 ==0:
                return False
            y = (x-3)//2
            if esieve[y] is False:
                return False
    return True


def Q357():
    #N = 100
    N = 100_000_000
    esieve, plist = sieve_of_erat(N)
    ans = 1 # 1 is a prime generating integer.
    # But, apart from 1 all the remaining prime generating integers are even and of the form 4n + 2
    for x in plist[1:]:
        n = x-1
        if n% 4 != 0:
            if is_prime_gen_integer(n, esieve):
                ans += n
    print("Answer is:", ans)
        

if __name__ == '__main__':
    import time
    start_time = time.time()
    Q357()
    print("Program run time(in s): ", (time.time() - start_time))