PE 131 Prime cube partnership （数论）

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

## Prime cube partnership ##

### Problem 131 ###

There are some prime values, *p*, for which there exists a positive integer, *n*, such that the expression *n*3 \+ *n*2*p* 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是否是素数就可以了。**

**代码：**

#include <bits/stdc++.h>
    using namespace std;
    
    vector<int> primes;
    int prime[1000000];
    void getPrimes()
    {	
        for(int i = 0 ; i < 1000000; i++){
            prime[i] = 1;   
        }
        for(int i = 2 ; i < 1000000; i++)
    	{
            if (prime[i])
    		{
                primes.push_back(i);
                if(i <= (int)sqrt((double)1000000))
    			{    
                    for(int t = i*i ; t<1000000 ; t+=i)//prime[i*i+k*i]=false
    				{   
                        prime[t] = 0;
                    }
                }
            }
        }
    }
    
    int solve(int n)
    {
     
      int ans = 0;
      for (int x = 1; x * x * 3 + x * 3 + 1 < n; x++)
      {
        if (prime[x * x * 3 + x * 3 + 1]){
        	ans++;
    	}
      }
      return ans;
    }
    
    int main()
    {
      getPrimes();
      cout<<"init finish!"<<endl;
      cout<<solve(1000000)<<endl;
      return 0;
    }