题意： 一个序列a, a+d,a+2d,……,a+nd; 给定a,d,n，找出第n个素数
有了之前的经验，直接空间换时间
#include<cstdio> #include<string.h> #include<algorithm> #include<cmath> #define MAXN 1000000 using namespace std; bool is_primes[MAXN];//判断质数 int primes[MAXN];//质数数组，从1开始 int prime_count;//质数数量 void GetPrimes(int n){ int k = 0; memset(is_primes, true, sizeof(is_primes)); is_primes[1] = false; for (int i = 2; i <= n; i++){ if (!is_primes[i]) continue; primes[++k] = i; for (int m = 2; m*i <= n; m++) is_primes[m*i] = false; } prime_count = k; } int main() { int a, d, n; GetPrimes(MAXN); while(scanf("%d%d%d", &a, &d, &n), a + d + n){ int num = 0, sum = 0; while(n){ sum = a + num * d; if(is_primes[sum]) n--; num++; } printf("%d\n", sum); } return 0; }