当前位置: 代码迷 >> 综合 >> Algorithm Gossip: 完美数优化版
  详细解决方案

Algorithm Gossip: 完美数优化版

热度:14   发布时间:2023-12-17 06:34:12.0
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 + "个");
    }
    
    
    
}
  相关解决方案