#!/bin/env python3

import time
import math

"""
https://projecteuler.net/problem=357

"""

start = time.time()


def primes(ubound=10**5):
    """ Generating prime numbers LIST
        https://stackoverflow.com/a/8627193/1770460
    """
    size = (ubound - 3) // 2
    a = [False] * size
    s = 0
    primes = []
    while s < size:
        t = 2 * s
        p = t + 3
        primes.append(p)
        for n in range(t * (s + 3) + 3, size, p):
            a[n] = True
        s = s + 1
        while s < size and a[s]:
            s = s + 1
    return primes

the_primes = primes()

def number_divisors(max_limit=10**5):
    """ Find the divisors of every number.
        Return it in a dict in the format:
        { number1: [divisor1, divisor2 ... ], .. }
    """
    num_divs = {}
    for i in range(4, max_limit):
        if i in the_primes:
            continue
        else:
            sq = math.sqrt(i)
            for n in range(2, int(sq) + 1):
                if i not in num_divs:
                    num_divs[i] = [1]
                if i % n == 0:
                    if n == i / n:
                        num_divs[i].append(n)
                    else:
                        num_divs[i].extend((n, i / n))
    return num_divs



def find_count(d):
    """ Check every number whether the divisors i.e. d + number / d is
        prime.
    """
    assert d is not None

    count = 0
    for number, list_divisors in d.items():
        all_primes = True
        for each_div in list_divisors:
            val = (each_div + (number / each_div))
            if val not in the_primes:
                all_primes = False
                break
        if all_primes:
            count += 1
    return count




if __name__ == '__main__':

    num_divisors = number_divisors()
    print(find_count(num_divisors))

    elapsed_time = (time.time() - start)
    print('time elapsed %s sec.' % elapsed_time)

the_primes = set(primes())

def primes(ubound=10**5):
    """ Generating prime numbers https://stackoverflow.com/a/8627193/1770460 """
    size = (ubound - 3) // 2
    a = [False] * size
    s = 0
    while s < size:
        t = 2 * s
        p = t + 3
        yield p
        for n in range(t * (s + 3) + 3, size, p):
            a[n] = True
        s = s + 1
        while s < size and a[s]:
            s = s + 1