PE 131 Prime cube partnership (数论)

冷不防 2022-07-13 13:18 174阅读 0赞

Prime cube partnership

Problem 131

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。

非常奇特的是,对于满足这个性质的素数,n的值都是唯一的。在小于一百的素数中,只有四个素数满足这个性质。

在小于一百万的素数中,有多少个素数满足这个神奇的性质?

题解:这题还是从数论上下手吧。

因为p是素数,n3+n2p=m3所以n^2(n+p)=m^3.

所以只能让n和n+p都为立方数, 所以这两个立方数相减的差就是一个素数p,

又因为a^3 - b^3 = (a-b)(a^2+ab+b^2),所以只有当a-b=1时,a^3 - b^3才可能是一个素数.

所以只需要检查相邻的2个立方数之差是否是素数就可以了.

即(n+1)^3-n^3=3n^2+3n+1。

所以这题就变成了只需要检查3n^2+3n+1是否是素数就可以了。

代码:

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector<int> primes;
  4. int prime[1000000];
  5. void getPrimes()
  6. {
  7. for(int i = 0 ; i < 1000000; i++){
  8. prime[i] = 1;
  9. }
  10. for(int i = 2 ; i < 1000000; i++)
  11. {
  12. if (prime[i])
  13. {
  14. primes.push_back(i);
  15. if(i <= (int)sqrt((double)1000000))
  16. {
  17. for(int t = i*i ; t<1000000 ; t+=i)//prime[i*i+k*i]=false
  18. {
  19. prime[t] = 0;
  20. }
  21. }
  22. }
  23. }
  24. }
  25. int solve(int n)
  26. {
  27. int ans = 0;
  28. for (int x = 1; x * x * 3 + x * 3 + 1 < n; x++)
  29. {
  30. if (prime[x * x * 3 + x * 3 + 1]){
  31. ans++;
  32. }
  33. }
  34. return ans;
  35. }
  36. int main()
  37. {
  38. getPrimes();
  39. cout<<"init finish!"<<endl;
  40. cout<<solve(1000000)<<endl;
  41. return 0;
  42. }

发表评论

表情:
评论列表 (有 0 条评论,174人围观)

还没有评论,来说两句吧...

相关阅读

    相关 PE1-什么是pe

    PE是什么? PE即 Portable Executable(可移植的执行体)。它是 Win32环境自身所带的执行体文件格式。它的一些特性继承自 Unix的 Coff 文