Project Euler #196: Prime triplets

Question

I did the HackerRank version of Project Euler #196 using Python 3.

My code ran successfully for 6 test cases out of 20. For test 14, it showed a timeout error which is not a functionality bug but because it takes more time in execution than given time constraint. I tried many times but I am not able to optimise it further to run successfully for all test cases. There are people who got all testcases passed. Please help me if someone could suggest better approach to reduce time of execution for this problem.

Problem description

Build a triangle from all positive integers in the following way:

Each positive integer has up to eight neighbours in the triangle.

A set of three primes is called a prime triplet if one of the three primes has the other two as neighbours in the triangle.

For example, in the second row, the prime numbers 2 and 3 are elements of some prime triplet.

If row 8 is considered, it contains two primes which are elements of some prime triplet, i.e. 29 and 31.

If row 9 is considered, it contains only one prime which is an element of some prime triplet: 37.

Define S(n) as the sum of the primes in row n which are elements of any prime triplet. Then S(8) = 60 and S(9) = 37.

You are given that S(10000) = 950007619.

Find S(a) + S(b).

Input Format

The only line of each test file contains exactly two integers separated by a single space: a and b.

Constraints

1 <= a, b <= 10⁷

Output Format

Output exactly one number that equals to S(a) + S(b).

Examples

Input 0:

8 9

Output 0:

97

Input 1:

9 10000

Output 1:

950007656

My code

import sys

def check_prime(num):
    counter=2
    flag=True
    while counter*counter <= num and flag:
        if num%counter == 0:
            flag=False
            break
        counter+=1     
    return flag

def find_delimeters(line_no):
    start_num = (((line_no-1)/2)*(line_no))+1
    end_num = int(start_num) + line_no -1
    return int(start_num), int(end_num)

def find_neighbours(num, line_no):
    position = find_position(num,line_no)
    if position == 'l_c':
        return {num+1:line_no, num-line_no+1:line_no-1, num-
                line_no+2:line_no-1, num+line_no:line_no+1,                                  
                num+line_no+1:line_no+1}
    elif position == 'r_c':
        return {num-1:line_no, num+line_no-1:line_no+1, 
                num+line_no:line_no+1, num-line_no:line_no-1,                                    
                num+line_no+1:line_no+1}
    elif position == 'r_2_c':
        return {num+1:line_no, num-1:line_no, num-line_no+1:line_no-1, 
                num-line_no:line_no-1, num+line_no:line_no+1,                      
                num+line_no+1:line_no+1, num+line_no-1:line_no+1}
    else:
        return {num+1:line_no, num-1:line_no, num-line_no+1:line_no-1, 
                num-line_no+2:line_no-1, num-line_no:line_no-                       
                1, num+line_no:line_no+1, num+line_no+1:line_no+1, 
                num+line_no-1:line_no+1}

def find_position(num, line_no):
    start, end = find_delimeters(line_no)
    if num == start:
        return 'l_c'
    elif num == end:
        return 'r_c'
    elif num == end-1:
        return 'r_2_c'
    else:
        return 'n'

def find_triplt_list(start, end, line_no):
    if line_no == 1:
        return []
    elif line_no == 2:
        return [2,3]
    else:
        prime_triplt_lst = []
        for i in range(start,end+1):
            if i%2 and check_prime(i):
                count_p = 0
                neighbours = find_neighbours(i, line_no)
                for j, line in neighbours.items():
                    if j%2 and check_prime(j):
                        count_p+=1
                        iter_val = [j,line]
                        if count_p >=2:
                            prime_triplt_lst.append(i)
                            break
                if count_p == 1:
                    count_p = 0
                    neighbours = find_neighbours(iter_val[0], 
                                                 iter_val[1])
                    for j, line in neighbours.items():
                        if j%2 and check_prime(j):
                            count_p+=1
                            if count_p >=2:
                                prime_triplt_lst.append(i)
                                break
                else:
                    continue
        return prime_triplt_lst


a,b=sys.stdin.readline().strip().split(' ')
a,b=int(a), int(b)
sum_a = 0
sum_b = 0
start_a, end_a = find_delimeters(a)
start_b, end_b = find_delimeters(b)
a_prime_triplt_lst = find_triplt_list(start_a, end_a, a)
b_prime_triplt_lst = find_triplt_list(start_b, end_b, b)

sys.stdout.write('%s' % 
                (sum(a_prime_triplt_lst)+sum(b_prime_triplt_lst)))

Answer 1

One big area for optimization is your check_prime function. First of all, you should keep track of whether you've already checked a number for primality:

def check_prime(n):
    if n in checked_for_primality:
         return(checked_for_primality[n])
    primality = check_for_primality(n)
    checked_for_primality[n] = primality
    return(primality)

(Note that if an if block has a return in it, you don't need to follow it with "else"; you won't get to what follows the if block unless the condition was false).

As for the check_for_primality function, you don't have to loop through every integer up to sqrt(n), you just have to loop through primes.

Your find_delimeters and check_position functions are rather useless. Just do start_num = int((((line_no-1)/2)*(line_no))+1) and end_num = int(int(start_num) + line_no -1), and then use start_num and end_num instead of start and end (note that end is a reserved word in many languages, so it's probably a good idea to not get in the habit of using that as a variable name). Instead of doing check_position, you can just replace position == 'l_c' with num==start_num, etc.

You could rewrite your find_neighbours function to add neighbors according to various conditions, rather than having a separate dictionary for each case. e.g.

neighbours = {}
if num != start_num:
     neighbours[num-1] = line_no
     neighbours[num-1+line_no] = line_no+1
     neighbours[num-1-line_no] = line_no-1
#etc

You could also write it as

neighbours = {}
for offset in [-1,0,1]
    if num != start_num:
        neighbours[num-1+line_num*offest] = line_no+offset
    #etc.

This would simplify the code at a slight cost to speed.

Another approach would be to do

primes_in_lines = {-1:{},0:{},1:{}}
for offset in [-1,0,1]:
    for position in range(line_no+offset)):
         value = start_num+offset*(line_num-1)+position
         if check_prime(value):
              primes_in_lines[offset][position] = value
for position in primes_in_lines[0].keys():
    count = 0
    for y in [-1,0,1]:
        for x in [-1,0,1]:
            if x in primes_in_lines[y].keys():
                count += 1

Answer 2

If you want to solve this efficiently, you will need a heavily modified sieve. Basically the idea is that by checking isprime repeatedly, you use lots of % operations, which are very slow. Instead, you can find primes from the begining of the previous row, to the end of the next row all at once using an offset sieve of Eratosthenes. This takes O((n-m)log(log(end-start))+sqrt(end)*log(log(end))) for these purposes, roughly O(end log log((end))). This can be very quick because numpy can be used for the calculations, all of which are addition and multiplication.

Once you've done this, you can use basically your algorithm, but you won't have to check for primes, which will speed things up a ton. Here is the sieve

def prime_sieve(lo,hi):
    k = int(hi**.5)+1
    a = np.ones(k,dtype=np.bool)
    b = np.ones(hi-lo,dtype=np.bool)

    for i in range(2, k):
        if a[i]:
            a[np.arange(i**2, k, i)] = False
            b[np.arange(i**2-lo, hi-lo, i)] = False
    return lo + np.where(b)[0]