HDU - 2866- Special Prime【数论】题解

傷城~ 2021-07-25 00:10 367阅读 0赞

### 目录 ###

*   *   *  1.题目
         *  2.代码

### 1.题目 ###

Give you a prime number p, if you could find some natural number (0 is not inclusive) n and m, satisfy the following expression:  
![在这里插入图片描述][20200616204044322.png]  
We call this p a “Special Prime”.  
AekdyCoin want you to tell him the number of the “Special Prime” that no larger than L.  
For example:  
If L =20  
1^3 + 7*1^2 = 2^3  
8^3 + 19*8^2 = 12^3  
That is to say the prime number 7, 19 are two “Special Primes”.  
**Input**  
The input consists of several test cases.  
Every case has only one integer indicating L.(1<=L<=10^6)  
**Output**  
For each case, you should output a single line indicate the number of “Special Prime” that no larger than L. If you can’t find such “Special Prime”, just output “No Special Prime!”  
**Sample Input**  
7  
777  
**Sample Output**  
1  
10

### 2.代码 ###

#include<iostream>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    const int maxn=1e6+10;
    int prime[maxn],ans[maxn];
    void isprime()
    { 
    	prime[0]=1;
    	prime[1]=1;
    	for(int i=2;i<maxn;i++)
    	{ 
    		if(prime[i]==0)
    		{ 
    			for(int j=i+i;j<maxn;j+=i)
    			 prime[j]=1;
    		}
    	}
    }
    bool  judge(int p)//判断12*P-3是否是平方数 
    { 
    	int m=12*p-3;
    	int k=(int)sqrt(m);
    	return  k*k==m;
    }
    void table()
    { 
       for(int i=1;i<maxn;i++)
       { 
          if(!prime[i]&&judge(i))	
             ans[i]++;
          ans[i]+=ans[i-1];
          
       }	
    } 
    int main()
    { 
    	isprime();
    	table();
    	int  l;
     	while(cin>>l)
     	{ 
     	   if(ans[l])
    		 cout<<ans[l]<<endl;
    	   else
    	     cout<<"No Special Prime!"<<endl;	
    	}
    	return 0;
    }

[20200616204044322.png]: /images/20210724/2980aa21d82746f6b03ccaa5c010db80.png