Java語(yǔ)言求解完美數(shù)代碼分析
1、概念
首先我們理解一下,什么叫做完美數(shù)?
問(wèn)題描述:若一個(gè)自然數(shù),它所有的真因子(即除了自身以外的約數(shù))的和恰好等于它本身,這種數(shù)叫做完全數(shù)。簡(jiǎn)稱“完數(shù)”
例如,
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
按照完數(shù)的定義,其實(shí)用程序求解完數(shù)并不是太難,先求解出這個(gè)數(shù)的所有真因子,然后相加,判斷是否等于它本身即可。但是,在這個(gè)數(shù)很小的時(shí)候,沒(méi)有什么問(wèn)題,一旦這個(gè)數(shù)字超過(guò)一定的數(shù)值,那么問(wèn)題就來(lái)了,程序的執(zhí)行效率就會(huì)變得低下。
我們優(yōu)化程序的算法邏輯,往往會(huì)考慮一個(gè)問(wèn)題,怎么高效的利用計(jì)算機(jī)的特性?在它所定義的算法中,有沒(méi)有大量重復(fù)的無(wú)用功呢?沿著這樣的思路去考慮這個(gè)問(wèn)題,我們會(huì)很快得到另外的一種解決方案。
2、說(shuō)明
2.1分析
在這里,我們會(huì)不會(huì)很容易就想到,之前我們提到過(guò)的分解因式?是的,在解決完美數(shù)的時(shí)候,我們會(huì)用到分解因式。一般來(lái)說(shuō),求解完美數(shù)會(huì)經(jīng)過(guò)三個(gè)步驟:
1.求出一定數(shù)目的質(zhì)數(shù)表
2.利用質(zhì)數(shù)表求指定數(shù)的因式分解
3.利用因式分解求所有真因數(shù)和,并檢查是否為完美數(shù)
2.2難點(diǎn)
初看之下,第一步和第二步是沒(méi)什么問(wèn)題的,我們?cè)谇懊娴膬善恼轮幸呀?jīng)探討過(guò)了,不清楚的同學(xué)可以查看。
重點(diǎn)是在第三步,如何求真因數(shù)和?方法很簡(jiǎn)單,要先知道將所有真因數(shù)(有不清楚真因數(shù)概念的同學(xué),去看看)和加上該數(shù)本身,會(huì)等于該數(shù)的兩倍(有些同學(xué)不知道,現(xiàn)在應(yīng)該也知道了吧?),例如:
2 * 28 = 1 + 2 + 4 + 7 + 14 + 28
事實(shí)上,這段等式可以轉(zhuǎn)換為:(代碼輸入錯(cuò)誤,我用截圖好了)
發(fā)現(xiàn)沒(méi)有?2和7都是因式分解得到的,那么,程序是不是有了簡(jiǎn)化的地方?
2.3結(jié)論
只要求出因式分解,就可以利用循環(huán)求得等式后面的值,將該值除以2就是真因數(shù)和了;等式后面第一眼看時(shí)可能想到使用等比級(jí)數(shù)公式來(lái)解,不過(guò)會(huì)使用到次方運(yùn)算,可以在進(jìn)行讀取因式分解陣列時(shí),同時(shí)計(jì)算出等式后面的值。
3、代碼
import java.util.ArrayList; // 求解完美數(shù) public class PerfectNumber { // 傳入一個(gè)值,求解至少多少個(gè)完美數(shù) 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(); } }
總結(jié)
以上就是本文關(guān)于Java語(yǔ)言求解完美數(shù)代碼分析的全部?jī)?nèi)容,希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題,如有不足之處,歡迎留言指出!
相關(guān)文章
Spring Cloud Data Flow初體驗(yàn)以Local模式運(yùn)行
這篇文章主要介紹了Spring Cloud Data Flow初體驗(yàn)以Local模式運(yùn)行,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-08-08Spring?Boot2.6.0新特性之默認(rèn)禁止循環(huán)引用
Spring?Boot2.6.0為我們帶來(lái)很多好用的新特性/改進(jìn),這篇文章主要給大家介紹了關(guān)于Spring?Boot2.6.0新特性之默認(rèn)禁止循環(huán)引用的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-02-02如何搭建一個(gè)完整的Java開(kāi)發(fā)環(huán)境
這篇文章主要教大家如何搭建一個(gè)完整的Java開(kāi)發(fā)環(huán)境,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2017-11-11Java IO流對(duì)象的序列化和反序列化實(shí)例詳解
這篇文章主要介紹了Java IO流對(duì)象的序列化和反序列化實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-05-05spring boot國(guó)際化之MessageSource的使用方法
這篇文章主要給大家介紹了spring boot國(guó)際化之MessageSource使用的相關(guān)資料,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11Java如何基于command調(diào)用openssl生成私鑰證書
這篇文章主要介紹了Java如何基于command調(diào)用openssl生成私鑰證書,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-08-08