練習 － Dirichlet’s Theorem on Arithmetic Progressions

Dirichlet’s Theorem on Arithmetic Progressions

題目：如果a和d是互質的正整數，從a開始增加d的算術序列，即a，a + d，a + 2d，a + 3d⋯⋯包含無窮多的質數。這被稱為Dirichlet算術級數定理。列出正整數a、d和n，寫一個程式陷出算術序列中第n個質數。

輸入：輸入是一個數據集合的序列，一個數據集合一行，包含了3個用空格分開的正整數a、d和n。a和d互質，設定a<=9307，d<=346，n<=210。輸入值若有0則為結束。

輸出：輸出行與輸入的數據集合的行數相同。每行列出一個整數，並且不包含多餘的字元。輸出的整數相對應於資料集合a、d、n，是從a開始每次增加d的算術序列中第n個質數。

import java.util.Scanner;

public class DirichletsTheoremonArithmeticProgressions {

	public static boolean isPrimeNumberSqrt(int n) { //判斷是否為質數，使用檢查2~sqrt(n)方法
		if(n % 2 == 0 && n != 2)
			return false;
		for(int i = 3; i*i <= n; i += 2)
			if(n % i == 0)
				return false;
		return true;
	}

	public static void main(String[] args) {
		int aMax = 9307, dMax = 346, nMax = 210; //三項輸入條件數值的最大值
		int a, d, n; //記得當次的輸入條件數值
		Scanner scanIn = new Scanner(System.in); //輸入1組資料
        	a = scanIn.nextInt();
        	d = scanIn.nextInt();
        	n = scanIn.nextInt();
        	while(a > 0 || d > 0 || n > 0) { //若輸入值不大於結束程式
        		if(a > aMax) //超過最大值需重新輸入
        			System.out.println("起始值a超出範圍");
        		else if(a > aMax)
        			System.out.println("增量d超出範圍");
        		else if(a > aMax)
        			System.out.println("質數順序n超出範圍");
        		else {
	        		if(a % d != 0 && d % a != 0) { //判段起始值a和增量d是否為互質（一個質數，另一個不為它的倍數，這兩個數互質）
	        			int cnt = 0;
	        			int m;
	        			for(m = a; cnt < n; m += d) {
	        				if(isPrimeNumberSqrt(m)) cnt ++;
	        			}
	        			System.out.printf("%d\n", m - d);
	        		} else {
	        			System.out.println("a和d不為互質數");
	        		}
        		}
        		scanIn = new Scanner(System.in);
        		a = scanIn.nextInt();
            		d = scanIn.nextInt();
            		n = scanIn.nextInt();
        	}
	}
}

求質數還有很多定理可以使用，在這題上我只是用了2~sqrt(n)的技巧，還有埃拉托斯特尼篩法，或最愚蠢的2~(n-1)等等。