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

时间: 2017-11-28

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

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

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分词 2倒排索引 我们先看分词算法 目前对中文分词有两个方向,其中一个是利用概率的思想对文章分词. 也就是如果两个字,一起出现的频率很高的话,我们可以假设这两个字是一个词.这里可以用一个公式衡量:M(A,B)=P(AB)/P(A)P(B),其中 A表示一个字,B表示一个字,P(AB)表示AB相邻出现的概率,P(A)表示A在这篇文章中的频度,P(B)表示B在这篇文章中的频度.用概率分词的好

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 蒙特卡洛算法求圆周率近似值实例详解

起源 [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数据结构和算法(有序数组和二分查找)

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

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

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

python快速查找算法应用实例

本文实例讲述了Python快速查找算法的应用,分享给大家供大家参考. 具体实现方法如下: import random def partition(list_object,start,end): random_choice = start #random.choice(range(start,end+1)) #把这里的start改成random()效率会更高些 x = list_object[random_choice] i = start j = end while True: while li

PHP有序表查找之插值查找算法示例

本文实例讲述了PHP有序表查找之插值查找算法.分享给大家供大家参考,具体如下: 前言: 在前面我们介绍了二分查找,但是我们考虑一下,为什么一定要折半呢?而不是折四分之一或者更多? 打个比方,在英文词典里查找"apple",你下意识里翻开词典是翻前面的书页还是后面的书页呢?如果再查"zoo",你又会怎么查?显然你不会从词典中间开始查起,而是有一定目的地往前或往后翻. 同样,比如要在取值范围在 0 ~ 10000 之间的100个元素从小到大均匀分布的数组中查找5,我们自

Java实现的两种常见简单查找算法示例【快速查找与二分查找】

本文实例讲述了Java实现的两种常见简单查找算法.分享给大家供大家参考,具体如下: 前言: 查找是指从一批记录当中找出满足制定条件的某一记录的过程. 在平常的程序的编写当中很多时候时用得上的,这里简单介绍两个查找算法 1. 快速查找: 这个是相当简单的,以数组举例,就用一个for循环去查找数组中需要查找的数据 例子: public static boolean quickSearch(int a[], int x) { boolean f = false; int length = a.leng

JavaScript数据结构之二叉树的查找算法示例

本文实例讲述了JavaScript数据结构之二叉树的查找算法.分享给大家供大家参考,具体如下: 前面文章介绍了二叉树的遍历,现在谈谈在二叉树中进行查找.对二叉查找树来说,一般有以下三类查找:最大值,最小值和给定值. 查找最小值就是遍历左子树,直到找到最后一个结点,这是因为在二叉查找树中较小的值总是在左子节点上的. 代码如下: function getMin(){//查找最小值 var current=this.root;//指向根节点 while(current.left!=null){ cur

java实现的统计字符算法示例

本文实例讲述了java实现的统计字符算法.分享给大家供大家参考,具体如下: 统计字符: 概述:给定字符串,将它们进行分类,分别的去统计它们的个数及其字符 分类的有:字母 数字 中文 空格 等等 算法思路分析: 分别统计即可: 下面给出代码:(代码仅供参考) package javastudy; public class Testit6 { public static void main(String[] args) { String str = "...天2气 :[1] aA"; //

Java实现的求逆矩阵算法示例

本文实例讲述了Java实现的求逆矩阵算法.分享给大家供大家参考,具体如下: package demo; public class MatrixInverse { public static double Det(double [][]Matrix,int N)//计算n阶行列式(N=n-1) { int T0; int T1; int T2; double Num; int Cha; double [][] B; if(N>0) { Cha=0; B=new double[N][N]; Num=

php实现的二分查找算法示例

本文实例讲述了php实现的二分查找算法.分享给大家供大家参考,具体如下: <?php $arr = array(4,58,11,34,88,45,32,54,63,78); function binary($arr,$bnum) { if(is_array($arr) && count($arr) > 0) { sort($arr); $start = 0; $end = count($arr)-1; $mid = -1; while($start <= $end) {

PHP二分查找算法示例【递归与非递归方法】

本文实例讲述了PHP二分查找算法.分享给大家供大家参考,具体如下: binarySearch 二分查找采用的方法比较容易理解,以数组为例: ① 先取数组中间的值floor((low+top)/2), ② 然后通过与所需查找的数字进行比较,若比中间值大,则将首值替换为中间位置下一个位置,继续第一步的操作:若比中间值小,则将尾值替换为中间位置上一个位置,继续第一步操作 ③ 重复第二步操作直至找出目标数字 比如从1,3,9,23,54 中查找数字23, 首位置为0, 尾位置为4,中间位置就为2 值为9