AOJ0053 Sum of Prime Numbers
問題リンク Sum of Prime Numbers
- 解法
素数ときたらエラトステネス。
ただ、どの大きさまで作ればいいか分からないので、一旦、10000個目の素数が何なのかを求めるプログラムを作りました。結果は104729です。
後は、大きさ104730の篩を作って、累積和を貯めていけば勝ちです。
- ソース
import java.util.Arrays; import java.util.Scanner; //Sum of Prime Numbers public class AOJ0053 { public static void main(String[] args) { boolean[] p = new boolean[104730]; int[] s = new int[10001]; int k=0; s[k++]=0; Arrays.fill(p, true); for(int i=2;i<104730;i++){ if(p[i]){ s[k]=s[k-1]+i; k++; for(int j=i*2;j<104730;j+=i)p[j]=false; } } Scanner sc = new Scanner(System.in); while(true){ int n = sc.nextInt(); if(n==0)break; System.out.println(s[n]); } } }