当前位置: 首页 > 编程笔记 >

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

漆雕欣德
2023-03-14
本文向大家介绍Java语言求解完美数代码分析,包括了Java语言求解完美数代码分析的使用技巧和注意事项,需要的朋友参考一下

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难点

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

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

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

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

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

2.3结论

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

3、代码

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;  
  } 
   
  html" target="_blank">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语言求解完美数代码分析的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出!

 类似资料:
  • 本文向大家介绍C语言完美实现动态数组代码分享,包括了C语言完美实现动态数组代码分享的使用技巧和注意事项,需要的朋友参考一下 我们知道,C语言中的数组大小是固定的,定义的时候必须要给一个常量值,不能是变量。 这带来了很大的不便,如果数组过小,不能容下所有数组,如果过大,浪费资源。 请实现一个简单的动态数组,能够随时改变大小,不会溢出,也不会浪费内存空间。 下面的代码实现了简单的动态数组: 运行结果:

  • 本文向大家介绍完美的ASP分页脚本代码,包括了完美的ASP分页脚本代码的使用技巧和注意事项,需要的朋友参考一下 直接写成函数的形式,如果输出生成好的页码,然后又程序输出或保存到文件中。 前十页为一批,第十页显示1,2,3…10;第十一页页码就变成了11,12…20 这种模式很多CMS都用到,比如5UCMS。函数名留点版权信息吧,cs=CatSeven 生成效果如下: #Page1:1 2 3 4

  • 本文向大家介绍C语言实现的统计素数并求和代码分享,包括了C语言实现的统计素数并求和代码分享的使用技巧和注意事项,需要的朋友参考一下 题目来源于PAT平台,此题又是费了一番脑子。题目要求输出给定区间内的素数个数并对他们求和。具体思路是利用循环判断素数,将结果传递给控制变量,由控制变量再来判断是否执行自增以及求和。当然这里必须要注意1既不是素数也不是合数。 下面是代码:

  • 主要内容:ISO 语言代码,ISO 639-1 语言代码ISO 语言代码 HTML 的 lang 属性可用于声明网页或部分网页的语言,这对搜索引擎和浏览器是有帮助的。 根据 W3C 推荐标准,您应该通过 <html> 标签中的 lang 属性对每张页面中的主要语言进行声明: 比如声明原文版语言: <html lang="en"> ... </html> 在 XHTML 中,采用如下方式在 <html> 标签中对语言进行声明: <html xmlns="

  • 本文向大家介绍易语言制作一款唯美的cookie分析工具的代码,包括了易语言制作一款唯美的cookie分析工具的代码的使用技巧和注意事项,需要的朋友参考一下 cookie分析源码 需要加载模块 Ex_DirectUI 3.0 DLL命令表 透明编辑框 对比代码 运行结果: 总结 以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对呐喊教程的支持。如果你想

  • 本文向大家介绍C语言统计字符个数代码分享,包括了C语言统计字符个数代码分享的使用技巧和注意事项,需要的朋友参考一下 C语言实现统计字符个数 再来一则C语言统计输入字符个数的代码 以上所述就是本文的全部内容了,希望大家能够喜欢