decadence

個人のメモ帳

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;
	}
}