普及组质数专题训练（10题精选）

题目1：基础质数判断（简单）

1  #include <iostream>
2  #include <cmath>
3  using namespace std;
4  
5  bool isPrime(int n) {
6      if (n <= 1) return false;
7      for (int i = 2; i <= sqrt(n); i++) {
8          if (n % i == 0) return false;
9      }
10     return true;
11 }
12 
13 int main() {
14     int n;
15     cin >> n;
16     
17     if (isPrime(n)) {
18         cout << n << "是质数" << endl;
19     } else {
20         cout << n << "不是质数" << endl;
21     }
22     
23     return 0;
24 }

选择题

1. 如果将第7行的i <= sqrt(n)改为i < n，输入n=100时，循环次数会：（ ）
   A. 从10次增加到100次
   B. 从10次减少到9次
   C. 保持不变
   D. 程序出错
   

2. 第6行if (n <= 1) return false;的作用不包括：（ ）
   A. 处理n=0的情况
   B. 处理n=1的情况
   C. 处理n=2的情况
   D. 处理n为负数的情况
   

3. 如果要优化算法，可以在第7行前添加代码快速排除偶数，以下哪段代码合适？（ ）
   A. if (n == 2) return true;
   B. if (n % 2 == 0) return n == 2;
   C. if (n < 2) return false;
   D. 以上都可以
   

4. 第8行的n % i == 0检查n是否能被i整除，如果改为n % i != 0，会导致：（ ）
   A. 算法结果反转（质数判断为合数，合数判断为质数）
   B. 所有数都被判断为质数
   C. 所有数都被判断为合数
   D. 程序死循环
   

5. 如果将第7行改为for (int i = 2; i * i <= n; i++)，有什么优点？（ ）
   A. 避免浮点数运算
   B. 提高精度
   C. 减少循环次数
   D. 以上都是
   

题目2：质因数分解（简单）

1  #include <iostream>
2  #include <vector>
3  using namespace std;
4  
5  vector<int> primeFactors(int n) {
6      vector<int> factors;
7      
8      for (int i = 2; i * i <= n; i++) {
9          while (n % i == 0) {
10             factors.push_back(i);
11             n /= i;
12         }
13     }
14     
15     if (n > 1) {
16         factors.push_back(n);
17     }
18     
19     return factors;
20 }
21 
22 int main() {
23     int n;
24     cin >> n;
25     
26     vector<int> factors = primeFactors(n);
27     
28     cout << n << " = ";
29     for (int i = 0; i < factors.size(); i++) {
30         if (i > 0) cout << " × ";
31         cout << factors[i];
32     }
33     cout << endl;
34     
35     return 0;
36 }

选择题

1. 第8行i * i <= n的循环条件，当n=13时，循环次数是：（ ）
   A. 0次
   B. 1次
   C. 2次
   D. 13次
   

2. 第9-12行的while循环如果改为if，输入n=8时，输出是：（ ）
   A. 8 = 2 × 2 × 2
   B. 8 = 2 × 4
   C. 8 = 2
   D. 8 = 8
   

3. 第15-17行的if语句处理什么情况？（ ）
   A. 处理n本身就是质数的情况
   B. 处理n大于1的剩余部分
   C. 都是
   D. 都不是
   

4. 如果将第8行改为for (int i = 2; i <= n; i++)，对n=100的影响是：（ ）
   A. 循环次数从10次增加到100次
   B. 循环次数从10次减少到9次
   C. 结果可能错误
   D. 没有影响
   

5. 第9行的n % i == 0中，当i=4时，能否进入循环？（ ）
   A. 能，如果n是4的倍数
   B. 不能，因为4不是质数
   C. 不能，因为循环不会检查i=4
   D. 不确定
   

题目3：埃拉托斯特尼筛法（中等）

1  #include <iostream>
2  #include <vector>
3  using namespace std;
4  
5  vector<int> sieveOfEratosthenes(int n) {
6      vector<bool> isPrime(n + 1, true);
7      vector<int> primes;
8      
9      isPrime[0] = isPrime[1] = false;
10     
11     for (int i = 2; i * i <= n; i++) {
12         if (isPrime[i]) {
13             for (int j = i * i; j <= n; j += i) {
14                 isPrime[j] = false;
15             }
16         }
17     }
18     
19     for (int i = 2; i <= n; i++) {
20         if (isPrime[i]) {
21             primes.push_back(i);
22         }
23     }
24     
25     return primes;
26 }
27 
28 int main() {
29     int n;
30     cin >> n;
31     
32     vector<int> primes = sieveOfEratosthenes(n);
33     
34     cout << "小于等于" << n << "的质数有: ";
35     for (int prime : primes) {
36         cout << prime << " ";
37     }
38     cout << endl;
39     
40     return 0;
41 }

选择题

1. 第13行的j = i * i而不是j = 2 * i，主要原因是：（ ）
   A. 避免重复标记
   B. 提高效率
   C. 两者都是
   D. 代码更简洁
   

2. 当n=30时，第11行外层循环的i值不会超过：（ ）
   A. 5
   B. 6
   C. 30
   D. 15
   

3. 如果将第13行改为for (int j = 2 * i; j <= n; j += i)，算法会：（ ）
   A. 结果正确但效率降低
   B. 结果错误
   C. 效率提高
   D. 死循环
   

4. 第19-23行的循环收集质数，如果将第20行的isPrime[i]改为true，会：（ ）
   A. 输出所有数字
   B. 输出所有质数
   C. 输出所有合数
   D. 程序崩溃
   

5. 第6行vector<bool> isPrime(n + 1, true)创建了大小为n+1的布尔数组，初始化值为true，这个操作的时间复杂度是：（ ）
   A. O(1)
   B. O(n)
   C. O(n²)
   D. O(log n)
   

题目4：线性筛法（欧拉筛）（中等偏难）

1  #include <iostream>
2  #include <vector>
3  using namespace std;
4  
5  vector<int> linearSieve(int n) {
6      vector<bool> isPrime(n + 1, true);
7      vector<int> primes;
8      
9      isPrime[0] = isPrime[1] = false;
10     
11     for (int i = 2; i <= n; i++) {
12         if (isPrime[i]) {
13             primes.push_back(i);
14         }
15         
16         for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
17             isPrime[i * primes[j]] = false;
18             if (i % primes[j] == 0) {
19                 break;
20             }
21         }
22     }
23     
24     return primes;
25 }
26 
27 int main() {
28     int n;
29     cin >> n;
30     
31     vector<int> primes = linearSieve(n);
32     
33     cout << "小于等于" << n << "的质数有: ";
34     for (int prime : primes) {
35         cout << prime << " ";
36     }
37     cout << endl;
38     
39     return 0;
40 }

选择题

1. 第18行的if (i % primes[j] == 0) break;作用是什么？（ ）
   A. 保证每个合数只被最小质因子标记
   B. 提前结束循环提高效率
   C. 避免重复标记
   D. 以上都是
   

2. 当i=4时，第16行的内层循环会标记哪些数为合数？（ ）
   A. 4×2=8
   B. 8
   C. 8和12
   D. 8, 12, 16
   

3. 如果不加第18-20行的break，算法会：（ ）
   A. 某些合数被多次标记
   B. 算法仍然正确但效率降低
   C. 可能漏掉某些合数
   D. 程序崩溃
   

4. 第16行的循环条件j < primes.size() && i * primes[j] <= n中，如果去掉第一个条件，当primes为空时会：（ ）
   A. 访问primes[0]导致段错误
   B. 循环不会执行
   C. 编译器报错
   D. 没有影响
   

5. 线性筛法与埃氏筛相比，主要优点是：（ ）
   A. 每个合数只标记一次
   B. 时间复杂度更低
   C. 空间复杂度更低
   D. 代码更简单
   

题目5：质因数分解优化（中等）

1  #include <iostream>
2  #include <vector>
3  using namespace std;
4  
5  vector<pair<int, int>> primeFactorsWithCount(int n) {
6      vector<pair<int, int>> factors;
7      
8      for (int i = 2; i * i <= n; i++) {
9          if (n % i == 0) {
10             int count = 0;
11             while (n % i == 0) {
12                 count++;
13                 n /= i;
14             }
15             factors.push_back({i, count});
16         }
17     }
18     
19     if (n > 1) {
20         factors.push_back({n, 1});
21     }
22     
23     return factors;
24 }
25 
26 int main() {
27     int n;
28     cin >> n;
29     
30     vector<pair<int, int>> factors = primeFactorsWithCount(n);
31     
32     cout << n << " = ";
33     for (int i = 0; i < factors.size(); i++) {
34         if (i > 0) cout << " × ";
35         cout << factors[i].first;
36         if (factors[i].second > 1) {
37             cout << "^" << factors[i].second;
38         }
39     }
40     cout << endl;
41     
42     return 0;
43 }

选择题

1. 第11-14行的while循环记录质因数的指数，如果改为if，输入n=8时，count的值是：（ ）
   A. 0
   B. 1
   C. 3
   D. 8
   

2. 第15行factors.push_back({i, count})创建了一个pair，这可以替换为：（ ）
   A. factors.push_back(make_pair(i, count))
   B. factors.emplace_back(i, count)
   C. 都可以
   D. 都不能
   

3. 第19-21行处理剩余的大于1的n，这个n一定是：（ ）
   A. 质数
   B. 合数
   C. 1
   D. 不确定
   

4. 第36-38行输出指数，如果指数为1则不输出指数，这行代码可以简化为：（ ）
   A. if (factors[i].second - 1) cout << "^" << factors[i].second;
   B. cout << (factors[i].second > 1 ? "^" + to_string(factors[i].second) : "");
   C. 都可以
   D. 都不能
   

5. 如果将第8行改为for (int i = 2; i <= n; i++)，对n=1000000的影响是：（ ）
   A. 循环次数从1000次增加到1000000次
   B. 循环次数从1000次减少到100次
   C. 结果可能错误
   D. 没有影响
   

题目6：米勒-拉宾素性测试（难）

1  #include <iostream>
2  #include <cmath>
3  using namespace std;
4  
5  long long power(long long a, long long d, long long n) {
6      long long result = 1;
7      a = a % n;
8      
9      while (d > 0) {
10         if (d % 2 == 1) {
11             result = (result * a) % n;
12         }
13         a = (a * a) % n;
14         d /= 2;
15     }
16     
17     return result;
18 }
19 
20 bool millerTest(long long d, long long n) {
21     long long a = 2 + rand() % (n - 4);
22     long long x = power(a, d, n);
23     
24     if (x == 1 || x == n - 1) {
25         return true;
26     }
27     
28     while (d != n - 1) {
29         x = (x * x) % n;
30         d *= 2;
31         
32         if (x == 1) return false;
33         if (x == n - 1) return true;
34     }
35     
36     return false;
37 }
38 
39 bool isPrimeMillerRabin(long long n, int k) {
40     if (n <= 1 || n == 4) return false;
41     if (n <= 3) return true;
42     
43     long long d = n - 1;
44     while (d % 2 == 0) {
45         d /= 2;
46     }
47     
48     for (int i = 0; i < k; i++) {
49         if (!millerTest(d, n)) {
50             return false;
51         }
52     }
53     
54     return true;
55 }
56 
57 int main() {
58     long long n;
59     cin >> n;
60     
61     if (isPrimeMillerRabin(n, 5)) {
62         cout << n << "可能是质数" << endl;
63     } else {
64         cout << n << "是合数" << endl;
65     }
66     
67     return 0;
68 }

选择题

1. 第5-18行的power函数实现了什么算法？（ ）
   A. 快速幂算法
   B. 模幂运算
   C. 快速幂取模
   D. 以上都是
   

2. 第10行的if (d % 2 == 1)可以替换为：（ ）
   A. if (d & 1)
   B. if (d % 2)
   C. 都可以
   D. 都不能
   

3. 第21行生成随机数a，范围是2到n-2，如果n很小（如n=5），n-4可能为：（ ）
   A. 1
   B. 负数
   C. 0
   D. 不确定
   

4. 第28-34行的while循环中，d最终会变为n-1，这是因为：（ ）
   A. 每次循环d乘以2
   B. 初始d是n-1的奇数部分
   C. 循环条件确保d最终等于n-1
   D. 以上都是
   

5. 第40行if (n <= 1 || n == 4) return false;中，为什么要单独处理n=4？（ ）
   A. 4是合数但不是奇数
   B. 4会导致随机数生成错误
   C. 4在后续测试中可能被误判
   D. 没有特别原因
   

题目7：区间质数统计（中等）

1  #include <iostream>
2  #include <vector>
3  #include <cmath>
4  using namespace std;
5  
6  int countPrimesInRange(int a, int b) {
7      if (b < 2) return 0;
8      a = max(a, 2);
9      
10     int n = b - a + 1;
11     vector<bool> isPrime(n, true);
12     
13     int sqrt_b = sqrt(b);
14     vector<bool> isPrimeSmall(sqrt_b + 1, true);
15     vector<int> primes;
16     
17     for (int i = 2; i <= sqrt_b; i++) {
18         if (isPrimeSmall[i]) {
19             primes.push_back(i);
20             for (int j = i * i; j <= sqrt_b; j += i) {
21                 isPrimeSmall[j] = false;
22             }
23         }
24     }
25     
26     for (int p : primes) {
27         int start = max(p * p, (a + p - 1) / p * p);
28         for (int j = start; j <= b; j += p) {
29             if (j >= a) {
30                 isPrime[j - a] = false;
31             }
32         }
33     }
34     
35     int count = 0;
36     for (int i = 0; i < n; i++) {
37         if (isPrime[i]) {
38             count++;
39         }
40     }
41     
42     return count;
43 }
44 
45 int main() {
46     int a, b;
47     cin >> a >> b;
48     
49     int count = countPrimesInRange(a, b);
50     cout << "区间[" << a << ", " << b << "]内的质数个数: " << count << endl;
51     
52     return 0;
53 }

选择题

1. 第27行的(a + p - 1) / p * p计算的是：（ ）
   A. 大于等于a的最小p的倍数
   B. 小于等于a的最大p的倍数
   C. a除以p的商
   D. a除以p的余数
   

2. 第30行的isPrime[j - a]中j - a的作用是：（ ）
   A. 将区间[a,b]映射到[0,n-1]
   B. 计算索引偏移
   C. 避免数组越界
   D. 以上都是
   

3. 第13行计算sqrt_b = sqrt(b)，如果改为int sqrt_b = (int)sqrt((double)b)，会：（ ）
   A. 更明确类型转换
   B. 提高精度
   C. 没有区别
   D. 可能出错
   

4. 第17-24行生成小质数，如果区间很大但b很小，这部分开销：（ ）
   A. 可以忽略
   B. 仍然很大
   C. 与a无关
   D. 与区间长度无关
   

5. 第28行的循环for (int j = start; j <= b; j += p)，如果p很大，start可能超过b，此时循环：（ ）
   A. 不会执行
   B. 执行一次
   C. 死循环
   D. 段错误
   

题目8：质数间距问题（难）

1  #include <iostream>
2  #include <vector>
3  #include <cmath>
4  #include <climits>
5  using namespace std;
6  
7  vector<int> findPrimes(int n) {
8      vector<bool> isPrime(n + 1, true);
9      vector<int> primes;
10     
11     isPrime[0] = isPrime[1] = false;
12     for (int i = 2; i <= n; i++) {
13         if (isPrime[i]) {
14             primes.push_back(i);
15             for (int j = i * i; j <= n; j += i) {
16                 isPrime[j] = false;
17             }
18         }
19     }
20     
21     return primes;
22 }
23 
24 pair<int, int> closestPrimes(int n) {
25     vector<int> primes = findPrimes(n);
26     
27     if (primes.size() < 2) {
28         return {-1, -1};
29     }
30     
31     int minGap = INT_MAX;
32     pair<int, int> result;
33     
34     for (int i = 1; i < primes.size(); i++) {
35         int gap = primes[i] - primes[i - 1];
36         if (gap < minGap) {
37             minGap = gap;
38             result = {primes[i - 1], primes[i]};
39         }
40     }
41     
42     return result;
43 }
44 
45 int main() {
46     int n;
47     cin >> n;
48     
49     auto result = closestPrimes(n);
50     
51     if (result.first == -1) {
52         cout << "范围内质数不足2个" << endl;
53     } else {
54         cout << "最接近的质数对: " << result.first << " 和 " << result.second << endl;
55         cout << "它们之间的差距: " << result.second - result.first << endl;
56     }
57     
58     return 0;
59 }

选择题

1. 第15行的j = i * i可能溢出，当i很大时，可以如何修改？（ ）
   A. 改为j = 2 * i
   B. 添加判断if (i <= n / i) for (int j = i * i; j <= n; j += i)
   C. 使用long long类型
   D. 以上都可以
   

2. 第27-29行处理特殊情况，如果primes为空，函数返回：（ ）
   A. {-1, -1}
   B. {0, 0}
   C. 程序崩溃
   D. 不确定
   

3. 第31行的INT_MAX来自哪个头文件？（ ）
   A. <climits>
   B. <limits>
   C. <cstdlib>
   D. <iostream>
   

4. 第36行的if (gap < minGap)如果改为if (gap <= minGap)，会：（ ）
   A. 返回最后一对最小间距的质数
   B. 返回第一对最小间距的质数
   C. 结果可能不同
   D. 没有区别
   

5. 第38行的result = {primes[i - 1], primes[i]}创建pair，这可以替换为：（ ）
   A. result = make_pair(primes[i - 1], primes[i])
   B. result.first = primes[i - 1]; result.second = primes[i];
   C. 都可以
   D. 都不能
   

题目9：哥德巴赫猜想验证（中等）

1  #include <iostream>
2  #include <vector>
3  using namespace std;
4  
5  vector<bool> sieve(int n) {
6      vector<bool> isPrime(n + 1, true);
7      isPrime[0] = isPrime[1] = false;
8      
9      for (int i = 2; i * i <= n; i++) {
10         if (isPrime[i]) {
11             for (int j = i * i; j <= n; j += i) {
12                 isPrime[j] = false;
13             }
14         }
15     }
16     
17     return isPrime;
18 }
19 
20 pair<int, int> goldbachConjecture(int n) {
21     if (n < 4 || n % 2 != 0) {
22         return {-1, -1};
23     }
24     
25     vector<bool> isPrime = sieve(n);
26     
27     for (int i = 2; i <= n / 2; i++) {
28         if (isPrime[i] && isPrime[n - i]) {
29             return {i, n - i};
30         }
31     }
32     
33     return {-1, -1};
34 }
35 
36 int main() {
37     int n;
38     cin >> n;
39     
40     auto result = goldbachConjecture(n);
41     
42     if (result.first == -1) {
43         cout << n << "不能表示为两个质数之和" << endl;
44     } else {
45         cout << n << " = " << result.first << " + " << result.second << endl;
46     }
47     
48     return 0;
49 }

选择题

1. 第21行的if (n < 4 || n % 2 != 0)处理了哪些无效输入？（ ）
   A. n小于4
   B. n是奇数
   C. 都是
   D. 都不是
   

2. 第27行的循环条件i <= n / 2而不是i < n，主要为了：（ ）
   A. 避免重复（如3+5和5+3）
   B. 提高效率
   C. 两者都是
   D. 没有特别原因
   

3. 第28行的isPrime[n - i]可能会访问数组的哪个位置？（ ）
   A. 0到n之间
   B. 0到n/2之间
   C. n/2到n之间
   D. 都有可能
   

4. 如果找到多个解，这个算法返回：（ ）
   A. 第一个找到的解
   B. 最后一个找到的解
   C. 所有解
   D. 最小的解
   

5. 第25行调用sieve(n)生成质数表，如果n很大但只需要验证一个数，可以如何优化？（ ）
   A. 只生成到n/2的质数表
   B. 使用更快的质数判断函数
   C. 使用概率性质数测试
   D. 以上都可以
   

题目10：回文质数（中等）

1  #include <iostream>
2  #include <vector>
3  #include <cmath>
4  using namespace std;
5  
6  bool isPalindrome(int n) {
7      int original = n;
8      int reversed = 0;
9      
10     while (n > 0) {
11         reversed = reversed * 10 + n % 10;
12         n /= 10;
13     }
14     
15     return original == reversed;
16 }
17 
18 bool isPrime(int n) {
19     if (n <= 1) return false;
20     for (int i = 2; i <= sqrt(n); i++) {
21         if (n % i == 0) return false;
22     }
23     return true;
24 }
25 
26 vector<int> findPalindromicPrimes(int n) {
27     vector<int> result;
28     
29     for (int i = 2; i <= n; i++) {
30         if (isPalindrome(i) && isPrime(i)) {
31             result.push_back(i);
32         }
33     }
34     
35     return result;
36 }
37 
38 int main() {
39     int n;
40     cin >> n;
41     
42     vector<int> primes = findPalindromicPrimes(n);
43     
44     cout << "小于等于" << n << "的回文质数: ";
45     for (int prime : primes) {
46         cout << prime << " ";
47     }
48     cout << endl;
49     
50     return 0;
51 }

选择题

1. 第10-13行的while循环反转数字，如果n=123，循环结束后reversed的值是：（ ）
   A. 321
   B. 123
   C. 0
   D. 32
   

2. 第30行的条件isPalindrome(i) && isPrime(i)，如果交换顺序为isPrime(i) && isPalindrome(i)，会：（ ）
   A. 提高效率，因为质数判断更耗时
   B. 降低效率
   C. 结果错误
   D. 没有影响
   

3. 第20行的i <= sqrt(n)可以优化，以下哪项不是优化方法？（ ）
   A. 改为i * i <= n
   B. 先判断偶数
   C. 从3开始，步长为2
   D. 使用质数表
   

4. 第6-16行的isPalindrome函数对于负数会：（ ）
   A. 返回false
   B. 进入无限循环
   C. 返回true
   D. 不确定
   

5. 第29行的循环从2开始，如果n很大，可以如何优化？（ ）
   A. 只检查奇数位回文数
   B. 生成回文数再判断质数
   C. 使用更快的质数判断
   D. 以上都可以