Problem 1141 : Dirichlet's Theorem on Arithmetic Progressions

keyword

素数　数論　Java

概要

互いに素な整数a,dが与えられたとき、初項a,公差dの等差数列でn番目に現れる素数を求める問題。
サイズが大きくないので愚直にやって間に合う。素数表はエラトステネスで。

import java.util.*;

class Main {

	static int ub = 1000010;
	static boolean isPrime[] = new boolean[ub];

	public static void main(String args[]){
		Scanner in = new Scanner(System.in);
		sieve();
		while(in.hasNext()){
			int a = in.nextInt(), d = in.nextInt(), n = in.nextInt();
			if(a==0 && d==0 && n==0) return ;
			int cnt = 0;
			for(int i = a;;i += d)if(isPrime[i] && ++cnt==n){
				System.out.println(i);
				break;
			}
		}
	}

	static void sieve(){
		for(int i=2; i<ub; i++) isPrime[i] = true;
		for(int i=2; i*i<ub; i++)if(isPrime[i]){
			for(int j=i*2; j<ub; j+=i){
				isPrime[j] = false;
			}
		}
	}
}