AOJ2101 Perfect Number

問題リンク Perfect Number

• 解法

1つのNあたり、O(√N)で判定できます。
i を1〜√Nの範囲だけ回し、Nを割り切るものを見つけたらそれは約数で、同時にN/iも約数です。
同じ数を重複して加算しないように注意が必要です。

• ソース

import java.util.Scanner;

//Perfect Number
public class AOJ2101 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			if(n==0)break;
			if(n==1){
				System.out.println("deficient number");
				continue;
			}
			int s = 1;
			for(int i=2;i*i<=n;i++){
				if(n%i==0){
					if(i*i==n)s+=i;
					else s+=i+n/i;
				}
			}
			System.out.println(n==s?"perfect number":n>s?"deficient number":"abundant number");
		}
	}
}