Project Euler 23
2つの過剰数の和で書き表せない正の整数の総和
- 過剰数リストの作成
- 過剰数和boolean配列の作成
条件とか所々注意が要るかも
ここでもi*i<=nにより時間削減
import java.util.*; class Sample { public static void main(String[] args){ final int NUM = 28123; ArrayList<Integer> al = new ArrayList<Integer>(); boolean number[] = new boolean[NUM]; int sum = 0; for(int i = 2; i < NUM; ++i){ if(abundant(i)) al.add(i); } for(int i = 0; i < al.size(); ++i){ for(int j = 0; j <= i && al.get(i)+al.get(j) < NUM; ++j){ number[al.get(i)+al.get(j)] = true; } } for(int i = 0; i < NUM; ++i){ if(!number[i]) sum += i; } System.out.println(sum); } private static boolean abundant(int num) { int sum=1; for(int i = 2; i*i <= num; ++i){ if((num%i)==0){ if(i == num/i) sum += i; else sum += i+num/i; } } if(sum > num) return true; else return false; } }