题目131：求使得n^3 + n^2 * p为完全立方数的质数p

欧拉计划

Prime cube partnership

There are some prime values, p, for which there exists a positive integer, n, such that the expression n³ + n²p is a perfect cube.

For example, when p = 19, 8³ + 8²×19 = 12³.

What is perhaps most surprising is that for each prime with this property the value of n is unique, and there are only four such primes below one-hundred.

How many primes below one million have this remarkable property?

题目：

对于某些质数 p，存在一个正整数 n，使得 n³ + n²p 是完全立方数。

例如，当 p=19 时，8³ + 8²×19 = 12³.

令人惊奇的是，对于每个具有上述性质的质数 p，对应的 n 是唯一的，而且 100 以下只有 4 个这样的质数。

一百万以下有多少质数具有上述性质？

fc1735

先暂时这样，等前面100多题都做了再回来弄质数列表优化代码

xor esi,esi
xor eax,eax
inc eax
xor ebx,ebx
xor ecx,ecx
add cl,3

_i:
add bx,6
add eax,ebx
cmp eax,1000000
jnc _ok
push cx
push eax
_d:
xor edx,edx
div ecx
cmp eax,ecx
jc _a
add cx,2
mov eax,[esp]
test edx,edx
jnz _d
jmp _n
_a:
inc esi
_n:
pop eax
pop cx
jmp _i

_ok:

所用时间: 0.00063秒

jerryxjr1220

"""
n^3+n^2*p=k^3 (p is prime, n and k are int)
n^3*(p/n+1)=k^3
n*((p+n)/n)^(1/3)=k
so, p+n and n need to be perfect cubes
let n = x^3 and p+n = y^3, then p=y^3-x^3=(y-x)*(y^2+x*y+x^2)
due to p is prime, so y-x must be 1, so p=(x+1)^3-x^3 and p must be prime and p < 1000000.
so, let's check x and y...
"""
primes=[True]*1000000
primes[:2]=[False]*2
for i,prime in enumerate(primes):
        if prime:
                for j in range(i*i, 1000000, i):
                        primes[j]=False
count = 0
for x in range(1, 1000):
        p = (x+1)**3-x**3
        if p >= 1000000:
                break
        if primes[p]:
                count += 1
print(count)

173