题目分析

本题要求我们找出给定算术序列中的第n个质数。算术序列的形式为：a, a + d, a + 2d, a + 3d,...，其中a和d是互质的正整数。根据Dirichlet定理，这个序列中包含无限多个质数。我们的任务是找到这个序列中的第n个质数。

解题思路

1. 预处理素数表：使用埃拉托斯特尼筛法预处理一定范围内的素数（如1,000,000），以便快速判断小范围内的数是否为素数。
2. 大数素数判断：对于超出预处理范围的数，使用试除法进行素数判断。
3. 生成算术序列：从a开始，每次增加d，生成序列中的数。
4. 统计素数：对每个生成的数进行素数判断，统计素数数量，直到找到第n个素数为止。

实现步骤

1. 预处理素数表：使用埃拉托斯特尼筛法生成1,000,000以内的素数表。
2. 输入处理：读取输入的a, d, n，直到遇到0 0 0为止。
3. 生成序列：从a开始，每次增加d，生成序列中的数。
4. 素数判断：
   • 如果数在预处理范围内，直接查表判断。
   • 如果数超出预处理范围，使用试除法判断。
5. 统计与输出：统计素数数量，直到找到第n个素数，输出结果。

优化思路

• 预处理范围选择：根据题目提示，结果不会超过1,000,000，因此预处理1,000,000以内的素数表即可覆盖大部分情况。
• 试除法优化：对于大数的素数判断，仅需检查到其平方根即可，且可以跳过偶数。

代码实现

#include <iostream>
#include <vector>
using namespace std;

// 埃拉托斯特尼筛法生成素数表
vector<bool> sieve(int max_num) {
    vector<bool> is_prime(max_num + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= max_num; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j <= max_num; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return is_prime;
}

// 试除法检查大数是否为素数
bool is_prime_large(int num) {
    if (num <= 1) return false;
    if (num == 2) return true;
    if (num % 2 == 0) return false;
    
    for (int i = 3; i * i <= num; i += 2) {
        if (num % i == 0) return false;
    }
    return true;
}

int main() {
    const int MAX = 1000000;
    vector<bool> is_prime = sieve(MAX);
    
    int a, d, n;
    while (cin >> a >> d >> n) {
        if (a == 0 && d == 0 && n == 0) break;
        
        int count = 0;
        int current = a;
        
        while (true) {
            bool prime_status = false;
            
            if (current <= MAX) {
                prime_status = is_prime[current];
            } else {
                prime_status = is_prime_large(current);
            }
            
            if (prime_status) {
                count++;
            }
            
            if (count == n) {
                cout << current << endl;
                break;
            }
            
            current += d;
        }
    }
    
    return 0;
}