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;
  } 

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

赞 (0)

相关推荐

  • Java实现合并两个有序序列算法示例

    本文实例讲述了Java实现合并两个有序序列算法.分享给大家供大家参考,具体如下: 问题描述 输入:序列A<a0,a1,a2,...aq,aq+1,aq+2,...,ar>,其中a0<a1<...<aq,aq+1<aq+2<...<ar 输出:序列B<b0,b1,...,br>,其中b0<b1<...<br 算法思想 创建一个长度为r的数组R,将A中的序列看作是两个有序序列 B=A<a0,a1,a2,...,aq> C

  • Java使用分治算法实现排序数索引功能示例【二分搜索】

    本文实例讲述了Java使用分治算法实现排序数索引功能.分享给大家供大家参考,具体如下: /** * Find the first q and return the index * First method is brutal force * Second may * be Divid and Conquer * * @author open201 * */ public class Ono { /** * f(n) = s.length = n; * * @param s * @param q

  • Java实现的最大匹配分词算法详解

    Java实现的最大匹配分词算法详解

    本文实例讲述了Java实现的最大匹配分词算法.分享给大家供大家参考,具体如下: 全文检索有两个重要的过程: 1分词 2倒排索引 我们先看分词算法 目前对中文分词有两个方向,其中一个是利用概率的思想对文章分词. 也就是如果两个字,一起出现的频率很高的话,我们可以假设这两个字是一个词.这里可以用一个公式衡量:M(A,B)=P(AB)/P(A)P(B),其中 A表示一个字,B表示一个字,P(AB)表示AB相邻出现的概率,P(A)表示A在这篇文章中的频度,P(B)表示B在这篇文章中的频度.用概率分词的好

  • Java常用HASH算法总结【经典实例】

    本文实例讲述了Java常用HASH算法.分享给大家供大家参考,具体如下: /** * Hash算法大全<br> * 推荐使用FNV1算法 * @algorithm None * @author Goodzzp 2006-11-20 * @lastEdit Goodzzp 2006-11-20 * @editDetail Create */ public class HashAlgorithms { /**//** * 加法hash * @param key 字符串 * @param prime

  • Java实现的快速查找算法示例

    本文实例讲述了Java实现的快速查找算法.分享给大家供大家参考,具体如下: 快速查找算法,可以根据想要找的是第几个大的数,每次循环都能固定下来一个数在数组完整排完序之后的位置,每次循环都能定一个数的位置,如果当前固定的数的位置和用户要找的第几个数匹配,则就直接返回.例如我要找第二大的数,如果循环一次固定的数的下标是1,那就是当前需要找的数. 代码如下: // 快速查找算法 public static int quickSelect(int[] arr, int selectIndex) { in

  • 详解Java数据结构和算法（有序数组和二分查找）

    一.概述 有序数组中常常用到二分查找,能提高查找的速度.今天,我们用顺序查找和二分查找实现数组的增删改查. 二.有序数组的优缺点 优点:查找速度比无序数组快多了 缺点:插入时要按排序方式把后面的数据进行移动 三.有序数组和无序数组共同优缺点 删除数据时必须把后面的数据向前移动来填补删除项的漏洞 四.代码实现 public class OrderArray { private int nElemes; //记录数组长度 private long[] a; /** * 构造函数里面初始化数组 赋值默

  • Java 蒙特卡洛算法求圆周率近似值实例详解

    起源 [1946: John von Neumann, Stan Ulam, and Nick Metropolis, all at the Los Alamos Scientific Laboratory, cook up the Metropolis algorithm, also known as the Monte Carlo method.]1946年,美国拉斯阿莫斯国家实验室的三位科学家John von Neumann,Stan Ulam 和 Nick Metropolis共同发明,

  • Java简单实现约瑟夫环算法示例

    Java简单实现约瑟夫环算法示例

    本文实例讲述了Java简单实现约瑟夫环算法.分享给大家供大家参考,具体如下: 1.算法背景: 罗马人攻占了乔塔帕特,41人藏在一个山洞中躲过了这场浩劫.这41个人中,包括历史学家josephus和他的一个朋友.剩余的39个人为了表示不向罗马人屈服,决定集体自杀.大家决定了一个自杀方案,所有这41人围城一个圆圈,由第一个人开始顺时针报数,没报数为3的人就立刻自杀,然后由下一个人重新开始报数 仍然是每报数为3的人就立刻自杀,......,知道所有人都自杀死亡为止. 约瑟夫和他的朋友并不想自杀,于是约

  • 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 按照完数的定义,其实用程序求解完数并不是太难,先求解出这个数的所有真因子,然后相加,判断是否等于它本身即可.但是,在这个数

  • java语言求解兔子问题代码分析

    1.思考 兔子问题,是费氏数列的形象化说法,它是由一位名为Fibonacci的数学家在它的著作中提出的一个问题. 2.描述 它体术的问题是:若有一只免子每个月生一只小免子,一个月后小免子也开始生产.起初只有一只免子,一个月后就有两只免子,二个月后有三只免子,三个月后有五只免子(小免子投入生产)...... 我们使用数学的方式表达出来,便是下面的一组数列: 1.1.2.3.5.8.13.21.34.55.89...... 注意:新生的小免子需一个月成长期才会投入生产!而且这些兔子是不死的哦!!!

  • Java语言实现反转链表代码示例

    问题描述 定义一个函数,输入一个链表的头结点,反转该链表并输出反转后的链表的头结点.链表结点如下: public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } 思路1: 要想反转链表,对于结点i,我们要把它的next指向它的前趋,因此我们需要保存前趋结点,同时,如果我们已经把i的next重新赋值,会无法找到i的后继,因此,在重新赋值之前,我们要保存i的后继. 代码:

  • Java语言实现数据结构栈代码详解

    近来复习数据结构,自己动手实现了栈.栈是一种限制插入和删除只能在一个位置上的表.最基本的操作是进栈和出栈,因此,又被叫作"先进后出"表. 首先了解下栈的概念: 栈是限定仅在表头进行插入和删除操作的线性表.有时又叫LIFO(后进先出表).要搞清楚这个概念,首先要明白"栈"原来的意思,如此才能把握本质. "栈"者,存储货物或供旅客住宿的地方,可引申为仓库.中转站,所以引入到计算机领域里,就是指数据暂时存储的地方,所以才有进栈.出栈的说法. 实现方式是

  • Java语言实现最大堆代码示例

    最大堆 最大堆的特点是父元素比子元素大,并且是一棵完全二叉树. data[1]开始存,data[0]空着不用.也可以把data[0]当成size来用. public class MaxHeap<T extends Comparable<? super T>> { private T[] data; private int size; private int capacity; public MaxHeap(int capacity) { this.data = (T[]) new

  • Java语言十大基础特性分析

    Java语言的作者们编写了具有广泛影响的Java白皮书,里面详细地介绍了他们的设计目标以及实现成果,还用简短的篇幅介绍了Java语言的特性.下面将对这些特性进行介绍. 1. 简单 Java语言的语法简单明了,容易掌握,而且是纯面向对象的语言.Java语言的简单性主要体现在以下几个方面: 语法规则和C++类似.从某种意义上讲,Java语言是由C和C++语言转变而来的,所以C程序设计人员可以很容易地掌握Java语言的语法. Java语言对C++进行了简化和提高.例如,Java使用接口取代了多重继承,

  • 用Java打印九九除法表代码分析 原创

    可能你已经学会了如何在Java中用循环语句打印九九乘法表,但学习是一个需要能够举一反三的事情,接下来,我们就来看看如何使用for循环语句打印九九除法表. 代码(九九除法表): public class TestNineNine { public static void main(String[] args) { for(int b=1;b<=9;b++) { for(int a=1;a<=9;a++) { int c = a*b; System.out.print(c+"/"

  • 邻接表无向图的Java语言实现完整源码

    邻接表无向图的Java语言实现完整源码

    邻接表无向图的介绍 邻接表无向图是指通过邻接表表示的无向图. 上面的图G1包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7条边. 上图右边的矩阵是G1在内存中的邻接表示意图.每一个顶点都包含一条链表,该链表记录了"该顶点的邻接点的序号".例如,第2个顶点(顶点C)包含的链表所包含的节点的数据分别是"0,1,3":而这"

  • Java实现求解一元n次多项式的方法示例

    Java实现求解一元n次多项式的方法示例

    本文实例讲述了Java实现求解一元n次多项式的方法.分享给大家供大家参考,具体如下: 项目需要做趋势预测,采用线性拟合.2阶曲线拟合和指数拟合的算法,各种线性拟合算法写成矩阵大概是这么个形式: 其中x是横坐标采样值,y是纵坐标采样值,i是采样点序列号,a是系数,N是采样点个数,n是阶数,所以线性拟合最后就转成了一个解高阶方程组的问题. 不知道有没有什么好用的java矩阵运算的包,我很不擅长搜集这种资料,所以只好捡起了已经放下多年的线性代数,自己写了个java程序用增广矩阵的算法来解高阶方程组.直

  • 深入了解Java语言中的并发性选项有何不同

    前言 Java™ 工程师在努力让并发性容易为开发人员所用.尽管做了不少的改进,但并发性仍然是 Java 平台的一个复杂.容易出错的部分.一部分复杂之处在于理解语言本身中的并发性的低级抽象,这些抽象在您的代码中填满了同步的代码块.另一个复杂之处来自一些新库,比如 fork/join,这些库在某些场景中非常有用,但在其他场景中收效甚微.了解容易混乱的大量低级选项需要专业经验和时间. 脱离 Java 语言的优势之一是,能够改善和简化并发性等区域.每种 Java 下一代语言都为此问题提供了独特的答案,利

随机推荐