题目131：求使得n^3 + n^2 * p为完全立方数的质数p
本帖最后由 永恒的蓝色梦想 于 2020-6-3 19:09 编辑Prime cube partnership
There are some prime values, p, for which there exists a positive integer, n, such that the expression n3 + n2p is a perfect cube.
For example, when p = 19, 83 + 82×19 = 123.
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，使得 n3 + n2p 是完全立方数。
例如，当 p=19 时，83 + 82×19 = 123.
令人惊奇的是，对于每个具有上述性质的质数 p，对应的 n 是唯一的，而且 100 以下只有 4 个这样的质数。
一百万以下有多少质数具有上述性质？
先暂时这样，等前面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,
test edx,edx
jnz _d
jmp _n
_a:
inc esi
_n:
pop eax
pop cx
jmp _i
_ok:
所用时间: 0.00063秒 """
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=*1000000
primes[:2]=*2
for i,prime in enumerate(primes):
if prime:
for j in range(i*i, 1000000, i):
primes=False
count = 0
for x in range(1, 1000):
p = (x+1)**3-x**3
if p >= 1000000:
break
if primes:
count += 1
print(count)
173
页:
[1]