#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @File Name: problem_131.py
# @Author: Copyright (c) 2017-06-14 15:46:47 Gillett Hernandez
# @Date:   2017-06-14 15:46:47
# @Last Modified by:   Gillett Hernandez
# @Last Modified time: 2017-08-10 13:11:18

from euler_funcs import *

# previous solution used the fact that
# solutions to n**3 + n**2*p == k**3
# took the form of n = c**3
# and c**9 + c**6*p == k**3 can be easily checked through all the primes below 1000000
@timed
def main():
    LIMIT = 1000000
    primes = get_primes(limit=1000000)
    diffs = [3*i**2 + 3*i + 1 for i in range(1,LIMIT)]

    count = 0
    for diff in diffs:
        if diff in primes:
            count += 1
        if diff >= LIMIT:
            break
    print(count)

if __name__ == '__main__':
    main()
