Algorithm Gossip: 完美数优化版

本文主要是介绍Algorithm Gossip: 完美数优化版，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

package main01;

import java.util.ArrayList;
import java.util.Scanner;
/**
 *
 * @author 欧阳子木
 *
 */
public class CoreJava {

    /**
     * .Algorithm Gossip: 完美数 说明如果有一数n，其真因数（Proper factor）的总和等于n，则称之为完美数（Perfect
     * Number），例如以下几个数都是完美数：
     *  6 = 1 + 2 + 3
     * 28 = 1 + 2 + 4 + 7 + 14
     * 496 = 1 + 2 +4 + 8 + 16 + 31 + 62 + 124 + 248
     * 由上式可知 2 * 28 = 1 + 2 + 4 + 7 + 14 + 28
     * 观察上式可得
     * 2 * 28 = (2 ^ 0 + 2 ^ 1 + 2 ^ 2) * (7 ^ 0 + 7 ^ 1)
     *
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner input = new Scanner(System.in);
        System.out.println("输入一个数字");
        PerfectNumber(input.nextInt());
        input.close();
    }

    // 第一步求得一定数量的质数集合
    public static ArrayList<Integer> Eratosthenes(int number) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        int i = 0;
        int j = 0;
        int array[] = new int[number + 1];
        // 初始化数组不考虑1
        for (i = 2; i <= array.length - 1; i++) {
            array[i] = 1;
        }
        for (i = 2; i <= array.length - 1; i++) {
            // 从2开始凡是为2得倍数，3的倍数，4的倍数。。。。。。则将该值设为0
            for (j = i * i; j <= array.length - 1; j += i) {
                array[j] = 0;
            }
        }
        //
        for (i = 2; i <= array.length - 1; i++) {
            if (array[i] == 1) {
                list.add(i);
            }
        }
        return list;
    }
//得到质因数集合
    public static ArrayList<Integer> isAll_factor(int number) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        ArrayList<Integer> temp_List = Eratosthenes(number);
        for (int i = 0; temp_List.get(i) * temp_List.get(i) <= number;) {
            if (number % temp_List.get(i) == 0) {
                list.add(temp_List.get(i));
                number = number / temp_List.get(i);
            } else {
                i++;
            }

        }
        list.add(number);

        return list;
    }
    //因数求和,并判断是否为完美数
    public static boolean isPerfectNumber(ArrayList<Integer> list, int number) {
        int i = 0;
        int temp2 = 1;
        int temp3 = 1;
        int sum = 1;
        //思想：2 * 28 = (2 ^ 0 + 2 ^ 1 + 2 ^ 2) * (7 ^ 0 + 7 ^ 1)
        while (i < list.size()) {
            do {
                temp2 *= list.get(i);
                temp3 += temp2;
                i++;
            } while (i < list.size() - 1 && list.get(i - 1) == list.get(i));
            sum *= temp3;
            temp2 = 1;
            temp3 = 1;
        }
        if (sum == 2 * number) {
            return true;
        }
        return false;
    }
    //重复调用该方法,判断指定范围内的完美数，并输出其个数
    public static void PerfectNumber(int number){
        int count = 0;
        for(int i = 2 ; i <= number; i++){
              if(isPerfectNumber(isAll_factor(i), i)){
                  System.out.println(i + "是个完美数");
                  count++;
              }
        }
        System.out.println("完美数个数为:" + count + "个");
    }
    
    
    
}

这篇关于Algorithm Gossip: 完美数优化版的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---