- POJ 3006 - Dirichlet’s Theorem on Arithmetic Progressions
- Time: 1000MS
- Memory: 65536K
- 难度: 初级
- 分类: 素数
0x00 POJ 原题
Description
If a and d are relatively prime positive integers, the arithmetic sequence beginning with a and increasing by d, i.e., a, a + d, a + 2d, a + 3d, a + 4d, …, contains infinitely many prime numbers. This fact is known as Dirichlet’s Theorem on Arithmetic Progressions, which had been conjectured by Johann Carl Friedrich Gauss (1777 - 1855) and was proved by Johann Peter Gustav Lejeune Dirichlet (1805 - 1859) in 1837.
For example, the arithmetic sequence beginning with 2 and increasing by 3, i.e.,
2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98, … ,
contains infinitely many prime numbers
2, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, … .
Your mission, should you decide to accept it, is to write a program to find the nth prime number in this arithmetic sequence for given positive integers a, d, and n.
Input
The input is a sequence of datasets. A dataset is a line containing three positive integers a, d, and n separated by a space. a and d are relatively prime. You may assume a <= 9307, d <= 346, and n <= 210.
The end of the input is indicated by a line containing three zeros separated by a space. It is not a dataset.
Output
The output should be composed of as many lines as the number of the input datasets. Each line should contain a single integer and should never contain extra characters.
The output integer corresponding to a dataset a, d, n should be the nth prime number among those contained in the arithmetic sequence beginning with a and increasing by d.
FYI, it is known that the result is always less than 10^(6) (one million) under this input condition.
Sample Input
367 186 151
179 10 203
271 37 39
103 230 1
27 104 185
253 50 85
1 1 1
9075 337 210
307 24 79
331 221 177
259 170 40
269 58 102
0 0 0Sample Output
92809
6709
12037
103
93523
14503
2
899429
5107
412717
22699
25673Source
0x10 题目概述
狄利克雷基于等差数列的算法原理
设一个等差数列，首元素为 a，公差为 b
现在要求输入 a,b,n，要求找出属于该等差数列中的第 n 个素数并输出
0x20 解题思路
见代码注释。
0x30 AC 源码
/*
Author: Exp
Date: 2017-11-30
Code: POJ 3006
Problem: Dirichlet's Theorem on Arithmetic Progressions
URL: http://poj.org/problem?id=3006
*/
/*
题意分析：
纯粹引用了狄利克雷数列，但其实没用到狄利克雷定理的问题。
狄利克雷数列即形如 a+nd 的等差数列，其中a、d互质（公约数只有1的两个自然数），n=1,2,3,......
已知在狄利克雷数列中，会出现无数个素数（这些质数模d同余a，但本题没用到这个特性）
现给定a和d，通过构造其狄利克雷数列，求数列中的第n个素数。
其中 a∈[1,9307], d∈[1,346], n∈[1,210]
解题思路：
这题的关键不是狄利克雷数列，还是求素数。
素数的范围可以通过 a、d、n 的最大值圈定（根据给定的数列参数最大值，约为100W以内的素数）
有了素数表之后就是暴力美学的工作了
① 用筛法求取题目给定最大范围内的所有素数
② 根据a、d构造狄利克雷数列，通过素数表找到其中第n个素数
③ 遍历数列时不要用 a+nd 公式，去掉乘法， 只用加法循环 a += d 即可
*/
#include <memory.h>
#include <math.h>
#include <iostream>
using namespace std;
const static int LEN = 1000000; // 自然数数组长度(求解素数范围)
const static int SQRT_NUM = ceil(sqrt((double) LEN)); // 根据合数定理得到的质因数范围
/*
* 使用筛法找出自然数范围内的所有素数
* @param primes 素数表
*/
void findPrimes(bool* primes);
/*
* 获取狄利克雷数列中第n个素数
* @param primes 素数集
* @param a 狄利克雷数列参数 a∈[1,9307]
* @param d 狄利克雷数列参数 b∈[1,346]
* @param n 期望得到素数序次 n∈[1,210]
* return 期望得到的第n个素数
*/
int getDirichletPrime(bool* primes, int a, int d, int n);
int main(void) {
bool primes[LEN]; // 素数集, 标记每个自然数是否为素数
findPrimes(primes); // 找出范围内所有素数
int a, d, n;
while(cin >> a >> d >> n &&
a != 0 && d != 0 && n != 0) { // 注意POJ测试用例中有个陷阱: a非质数,d=0,n>0, 若不单独约束d=0这个条件会因死循环导致TLE
int prime = getDirichletPrime(primes, a, d, n);
cout << prime << endl;
}
return 0;
}
void findPrimes(bool* primes) {
memset(primes, true, sizeof(bool) * LEN); // 注意memset是按字节覆写内存的
primes[0] = primes[1] = false;
for(int i = 2; i <= SQRT_NUM; i++) {
if(primes[i] == false) {
continue;
}
// 筛掉最小素数的所有倍数
int multiple = 2; // i的倍率（因不包括自身, 从2倍开始）
while(true) {
int mNum = i * multiple; // i的倍数
if(mNum >= LEN) {
break;
}
primes[mNum] = false;
multiple++;
}
}
}
int getDirichletPrime(bool* primes, int a, int d, int n) {
int prime = 0; // 第n个素数
for(int cnt = 0, dirichlet = a; cnt < n; dirichlet += d) {
if(primes[dirichlet] == true) {
prime = dirichlet;
cnt++;
}
}
return prime;
}
