Java语言求解完美数代码分析

时间:2022-05-29 05:38:29

1、概念

首先我们理解一下,什么叫做完美数?

问题描述:若一个自然数,它所有的真因子(即除了自身以外的约数)的和恰好等于它本身,这种数叫做完全数。简称“完数”

例如,

  6=1+2+3
  28=1+2+4+7+14
  496=1+2+4+8+16+31+62+124+248
  8128=1+2+4+8+16+32+64+127+254+508+1016+2032+4064

按照完数的定义,其实用程序求解完数并不是太难,先求解出这个数的所有真因子,然后相加,判断是否等于它本身即可。但是,在这个数很小的时候,没有什么问题,一旦这个数字超过一定的数值,那么问题就来了,程序的执行效率就会变得低下。

我们优化程序的算法逻辑,往往会考虑一个问题,怎么高效的利用计算机的特性?在它所定义的算法中,有没有大量重复的无用功呢?沿着这样的思路去考虑这个问题,我们会很快得到另外的一种解决方案。

2、说明

2.1分析

在这里,我们会不会很容易就想到,之前我们提到过的分解因式?是的,在解决完美数的时候,我们会用到分解因式。一般来说,求解完美数会经过三个步骤:

1.求出一定数目的质数表

2.利用质数表求指定数的因式分解

3.利用因式分解求所有真因数和,并检查是否为完美数

2.2难点

初看之下,第一步和第二步是没什么问题的,我们在前面的两篇文章中已经探讨过了,不清楚的同学可以查看。

重点是在第三步,如何求真因数和?方法很简单,要先知道将所有真因数(有不清楚真因数概念的同学,去看看)和加上该数本身,会等于该数的两倍(有些同学不知道,现在应该也知道了吧?),例如:

?
1
2 * 28 = 1 + 2 + 4 + 7 + 14 + 28

事实上,这段等式可以转换为:(代码输入错误,我用截图好了)

Java语言求解完美数代码分析

发现没有?2和7都是因式分解得到的,那么,程序是不是有了简化的地方?

2.3结论

只要求出因式分解,就可以利用循环求得等式后面的值,将该值除以2就是真因数和了;等式后面第一眼看时可能想到使用等比级数公式来解,不过会使用到次方运算,可以在进行读取因式分解阵列时,同时计算出等式后面的值。

3、代码

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import java.util.arraylist;
// 求解完美数
public class perfectnumber {
  // 传入一个值,求解至少多少个完美数
  public static int[] lessthan(int number) {
    int[] primes = prime.findprimes(number);
 
    arraylist list = new arraylist();
     
    for(int i = 1; i <= number; i++) { 
      int[] factors = factor(primes, i); 
      if(i == fsum(factors)) 
        list.add(new integer(i));
    
 
    int[] p = new int[list.size()];
    object[] objs = list.toarray(); 
    for(int i = 0; i < p.length; i++) {
      p[i] = ((integer) objs[i]).intvalue();
    }
     
    return p;
  }
   
  // 分解因式
  private static int[] factor(int[] primes, int number) { 
    int[] frecord = new int[number];
    int k = 0;
     
    for(int i = 0; math.pow(primes[i], 2) <= number;) { 
      if(number % primes[i] == 0) { 
        frecord[k] = primes[i]; 
        k++; 
        number /= primes[i]; 
      
      else
        i++; 
    
 
    frecord[k] = number; 
 
    return frecord; 
  
 
  // 因式求和
  private static int fsum(int[] farr) { 
    int i, r, s, q; 
 
    i = 0
    r = 1
    s = 1
    q = 1
 
    while(i < farr.length) { 
      do
        r *= farr[i]; 
        q += r; 
        i++; 
      } while(i < farr.length - 1 &&
          farr[i-1] == farr[i]); 
      s *= q; 
      r = 1
      q = 1
    
 
    return s / 2
  }
   
  public static void main(string[] args) {
    int[] pn = perfectnumber.lessthan(1000);
    
    for(int i = 0; i < pn.length; i++) {
      system.out.print(pn[i] + " ");
    }
     
    system.out.println();
  }
}

总结

以上就是本文关于java语言求解完美数代码分析的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出!

原文链接:http://blog.csdn.net/ljtyzhr/article/details/38962569