Project Eluer - 23

Non-abundant sums
Problem 23
A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.
A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.
As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.
Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.
翻訳(大意):
1つの数nの場合、そのすべての真の因子の和がnに等しい場合、nは完全数(例えば28,1+2+4+7+14=28であるため、28は完全数)と呼ばれる.nより小さく、nは不足数と呼ばれます.nより大きく、過剰数と呼ぶことができる.最小の過剰数は12(1+2+3+4+6=16、12より大きい)であるため、最小の2つの過剰数の和は12+12=24である.
数学的解析により、28123より大きいすべての数は2つの過剰数の和に書くことができる.正の整数の中で2つの過剰数の和に書けないすべての数の和を求める.
ソリューション:
題意によると、28123より大きい数はすべて2つの過剰数の和に書くことができ、すべての私たちは28123より小さい数に注目する必要があります.私の考えは:step 1:28124未満のすべての過剰数を求めて、step 2:1つの関数を書いて、入力パラメータはnで、すべての過剰数の中で、2つの和がnに等しいかどうかを計算して、step 3:step 2の戻り値に基づいて、結果を累積します.考え方は簡単ですが、コードを見てみましょう.
コード:

package projectEuler;

import java.util.ArrayList;

public class Problem23 {
	private static ArrayList<Integer> list;
	private static final int SIZE = 28123;

	public static void main(String[] args) {
		long start = System.currentTimeMillis();
		list = initAbundantList();
		int result = 0;
		for (int i = 1; i <= SIZE; i++) {
			result += (ifCanBeTheSumOfTwoAbundantNumber(i) ? 0 : i);
		}
		System.out.println("result:" + result);
		long end = System.currentTimeMillis();
		System.out.println("time:" + (end - start));
	}

	/*
	 *                   num
	 */
	private static boolean ifCanBeTheSumOfTwoAbundantNumber(int num) {
		int duration = findFirstIndexGreaterThanNum(num);
		for (int i = 0; i <= duration; i++) {
			for (int j = 0; j <= duration; j++) {
				if (num == (list.get(i) + list.get(j))) {
					// System.out.print("" + list.get(i) + "," + list.get(j));
					return true;
				}
			}
		}
		return false;
	}

	/*
	 *        ，      num       
	 */
	private static int findFirstIndexGreaterThanNum(int num) {
		int lengh = list.size();
		int i = 0;
		while (i < (lengh - 1) && list.get(i) < num) {
			i++;
		}
		return i;
	}

	/*
	 *        28123      
	 */
	private static ArrayList<Integer> initAbundantList() {
		ArrayList<Integer> list = new ArrayList<Integer>();
		for (int i = 1; i <= SIZE; i++) {
			if (countSumProperDivisor(i) > i) {
				list.add(i);
			}
		}
		return list;
	}

	/*
	 *  num        ，   
	 */
	private static int countSumProperDivisor(int num) {
		int sum = 0;
		int sqrtNum = (int) Math.sqrt(num);
		for (int i = 2; i <= sqrtNum; i++) {
			if (0 == num % i) {
				if (i == num / i) {
					sum += i;
				} else {
					sum += (i + num / i);
				}
			}
		}
		return sum + 1;
	}

	/*
	 *  num        ，   
	 */
	private static int countSumProperDivisor2(int num) {
		int sum = 0;
		int duration = (int) num / 2;
		for (int i = 1; i <= duration; i++) {
			if (0 == num % i) {
				sum += i;
			}
		}
		return sum;
	}
}

コードにコメントがあれば、あまり説明しません.考え方は上の解題と同じです.ここではいくつかの関数も分析します.
1つの数のすべての真の因子の和を求めるには、ここで2つの方法が提供されています.
求真因子の和:
方法1:この方法は2からsqrt(num)までの間の数を遍歴するだけで、1はすべての数で割り切れるので、直接後ろに1を加えることができて、私たちは直接2から計算することができます.1つの数を求めるたびに、実は1対で、例えば24、24/2=12なので、ここで私たちが求めたのは2つの数2と12、4と6が1対で、しかも法則を発見することができて、小さい数はすべてsqrt(num)より小さくて、すべての大きい数はすべてsqrt(num)より大きくて、だから私たちはこのように計算することができます.しかし、例えば25、最後に5*5=25と計算したとき、私たちは2つの数を加えることはできませんが、直接5を加えるべきです.はい、ここでこの考えを分析しました.

	/*
	 *  num        ，   
	 */
	private static int countSumProperDivisor(int num) {
		int sum = 0;
		int sqrtNum = (int) Math.sqrt(num);
		for (int i = 2; i <= sqrtNum; i++) {
			if (0 == num % i) {
				if (i == num / i) {
					sum += i;
				} else {
					sum += (i + num / i);
				}
			}
		}
		return sum + 1;
	}

方法2:第2の方法は少し時間がかかり、2からnum/2まで計算します.num/2より大きいすべての数がnumの真因子であるはずがないからです(考えてみればわかります).そこでここではnum/2以下の部分をすべて計算し、modができるかどうかを判断すればOKです.

	/*
	 *  num        ，   
	 */
	private static int countSumProperDivisor2(int num) {
		int sum = 0;
		int duration = (int) num / 2;
		for (int i = 1; i <= duration; i++) {
			if (0 == num % i) {
				sum += i;
			}
		}
		return sum;
	}

過剰数リストを求めるのは簡単ではありませんが、2つの過剰数の和が入力パラメータに等しいかどうかを判断する方法に重点を置いてみましょう.ここではまず、リスト内のすべての過剰数の和を組み合わせて配列に保存することができ、その後、各数を一度このリストに遍歴するだけで知ることができるという考え方を提供することができます.しかし,この方法はすべての過剰数列のうち任意の2つの数の和を要求するのは難しく,時間がかかりすぎる.私の考えを話してみましょう
1つの数numが入力されるたびに、numに等しくなるとループを終了し、trueを返す既存の過剰数リストで任意の2つの数の和を巡ります.ここで遍歴する範囲は速度を上げる鍵ですが、実際には2つの過剰数の和がnumに等しいとすると、過剰数はnumよりも小さいに違いありません(過剰数には0はありません)ので、後に関数findFirstIndexGreaterThanNum(int num)を書きます.名前から、実際に過剰数列の中にnumより小さい範囲が見つかっていることがわかります.そして私たちはifCanBeTheSumOfTwoAbundantNumber(int num)が範囲を縮小できると判断した.この範囲を見くびってはいけませんよ.計算回数を半分近く節約できます.コードは次のとおりです.

	/*
	 *                   num
	 */
	private static boolean ifCanBeTheSumOfTwoAbundantNumber(int num) {
		int duration = findFirstIndexGreaterThanNum(num);
		for (int i = 0; i <= duration; i++) {
			for (int j = 0; j <= duration; j++) {
				if (num == (list.get(i) + list.get(j))) {
					// System.out.print("" + list.get(i) + "," + list.get(j));
					return true;
				}
			}
		}
		return false;
	}

	/*
	 *        ，      num       
	 */
	private static int findFirstIndexGreaterThanNum(int num) {
		int lengh = list.size();
		int i = 0;
		while (i < (lengh - 1) && list.get(i) < num) {
			i++;
		}
		return i;
	}

はい、書き終わりました.結果は:
result:4179871 time:14711は15秒近くかかりますが、やはり遅いので、皆さんと交流してほしいですね.