题目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多题都做了再回来弄质数列表优化代码

1. 
   
2. xor esi,esi
   
3. xor eax,eax
   
4. inc eax
   
5. xor ebx,ebx
   
6. xor ecx,ecx
   
7. add cl,3
   
8. 
   
9. _i:
   
10. add bx,6
    
11. add eax,ebx
    
12. cmp eax,1000000
    
13. jnc _ok
    
14. push cx
    
15. push eax
    
16. _d:
    
17. xor edx,edx
    
18. div ecx
    
19. cmp eax,ecx
    
20. jc _a
    
21. add cx,2
    
22. mov eax,[esp]
    
23. test edx,edx
    
24. jnz _d
    
25. jmp _n
    
26. _a:
    
27. inc esi
    
28. _n:
    
29. pop eax
    
30. pop cx
    
31. jmp _i
    
32. 
    
33. _ok:
    

复制代码

所用时间: 0.00063秒

jerryxjr1220

1. """
   
2. n^3+n^2*p=k^3 (p is prime, n and k are int)
   
3. n^3*(p/n+1)=k^3
   
4. n*((p+n)/n)^(1/3)=k
   
5. so, p+n and n need to be perfect cubes
   
6. let n = x^3 and p+n = y^3, then p=y^3-x^3=(y-x)*(y^2+x*y+x^2)
   
7. 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.
   
8. so, let's check x and y...
   
9. """
   
10. primes=[True]*1000000
    
11. primes[:2]=[False]*2
    
12. for i,prime in enumerate(primes):
    
13.         if prime:
    
14.                 for j in range(i*i, 1000000, i):
    
15.                         primes[j]=False
    
16. count = 0
    
17. for x in range(1, 1000):
    
18.         p = (x+1)**3-x**3
    
19.         if p >= 1000000:
    
20.                 break
    
21.         if primes[p]:
    
22.                 count += 1
    
23. print(count)

复制代码

173