很显然这是一题有关于素数的题目。
?
注意数据的范围，爆搜超时无误。
?
这里要用到筛选法求素数。
?
筛选法求素数的大概思路是：
?
? ? ?如果a这个数是一个质数，则n*a不是质数。(年轻的孩子们不要纠结于判断a是否为素数）
?
? ? ?用一个数组实现就是：
?
? ? ?memset(prime,true,sizeof(prime));
?
? ? ?if (prime[i]) prime[i*j]=false;
?
? ? ?部分程序如下：
?
? ? ?
?
复制代码
const max=1000005;
bool prime[1000005]; ? ? ? ?
? ? ? ? memset(prime,true,sizeof(prime));
? ? for(i = 3 ; i <= ::max ; i ++ )
? ? {
? ? ? ? for(j = 3 ; j <= ::max/i ; j ++)
? ? ? ? {
? ? ? ? ? ? if(prime[i])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? prime[i * j] = false; ? ?
? ? ? ? ? ? } ? ?
? ? ? ? } ? ?
? ? }
复制代码
?
?
之后将中间进行小小的优化：
?
? ? ?我们知道偶数中，除了2，其他的都是合数。
?
? ? ?所以就可以将i++ 和 j++改成i+=2,j+=2;
?
? ? ?再将除2以外的偶数判为false;以及注意一下特殊的值： 1和0是false;(要记住，c++的数组是从0~max的,所以0要考虑在内）
?
?
?
优化后的程序如下：
?
? ? ?
?
复制代码
const int max = 1000005;
bool prime[1000005]={false};
? ??
? ? ? ? memset(prime,true,sizeof(prime));
? ? for(i = 3 ; i <= 1000 ; i += 2 )
? ? {
? ? ? ? for(j = 3 ; j <= ::max / i ; j += 2)
? ? ? ? {
? ? ? ? ? ? if(prime[i])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? prime[i * j] = false; ? ?
? ? ? ? ? ? } ? ?
? ? ? ? } ? ?
? ? }
? ? for(i = 4 ; i <= ::max; i += 2 )
? ? {
? ? ? ? prime[i] = false; ? ?
? ? }
? ? prime[1] = prime[0] = false;
? ??
复制代码
?
?
这样，这题就可以在我们拟好的素数表中找到第n个要求的素数。用一个简单的循环就可以搞定。。hoho
?
附上我的程序：
?
复制代码
#include
#include
using namespace std;
const int max = 1000005;
bool prime[1000005]={false};
int main()
{
? ? int ? ? ? ?i,a,d,n,j;
? ? memset(prime,true,sizeof(prime));
? ? for(i = 3 ; i <= 1000 ; i += 2 )
? ? {
? ? ? ? for(j = 3 ; j <= ::max / i ; j += 2)
? ? ? ? {
? ? ? ? ? ? if(prime[i])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? prime[i * j] = false; ? ?
? ? ? ? ? ? } ? ?
? ? ? ? } ? ?
? ? }
? ? for(i = 4 ; i <= ::max; i += 2 )
? ? {
? ? ? ? prime[i] = false; ? ?
? ? }
? ? prime[1] = prime[0] = false;
? ??
? ? while(cin >> a >> d >> n,a != 0 && d != 0 && n != 0)
? ? {
? ? ? ? j = 0;
? ? ? ? for (i = a; j < n; i += d)
? ? ? ? {
? ? ? ? ? ? if (prime[i])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? j++;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? cout << i - d << endl;
? ? }
? ? return 0;
}
?