AOJ1276 Prime Gap

AOJ Volume12

問題リンク Prime Gap

  • 概要

整数kのprime gapとは、k以下の最大の素数をp、k以上の最小の素数をp+nとしたときのnである。与えられる整数kのprime gapを答えよ。
2 <= k <= 1299709

  • 解法

エラトステネスの篩で1299709までの素数表を作り、kから出発して、pとp+nに相当するものを見つけます。

  • ソース
import java.util.Arrays;
import java.util.Scanner;

//Prime Gap
public class AOJ1276 {

	void run(){
		int N = 1299709;
		boolean[] p = new boolean[N+1];
		Arrays.fill(p, true);
		p[0]=p[1]=true;
		for(int i=2;i<=N;i++)if(p[i])for(int j=i+i;j<=N;j+=i)p[j]=false;
		Scanner sc = new Scanner(System.in);
		for(;;){
			int k = sc.nextInt();
			if(k==0)break;
			int l = k, r = k;
			while(!p[l])l--;
			while(!p[r])r++;
			System.out.println(r-l);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1276().run();
	}
}