C趣味程序(二)(12)求4位以內的相親數
2.6相親次數
2500年前,數學大師比戈·達拉斯發現220和284這兩個數字之間存在微妙的關系:
220的真因數之和爲:1 2 4 5 10 11 20 22 44 55 110 = 284。
相親人數的直接提陞就是相親鏈:以鏈條的形式出現的相親人數。擧個例子,如果A的真因子之和是B,B的真因子之和是C,C的真因子之和是D,最後D的真因子之和是A,那麽A,B,C,D就叫做4環盲數鏈。
數學界在尋找相親人數和相親鏈,但打破相親記錄的熱情不減。
2.6.1 求4位以內的相親數
1.算法分析
對指定區間中的每一個整數i應用試商實施窮擧判別。根據相親數的定義,用試商法(i mod j=0)找出i的所有小於i的真因數j,竝求出真因數的和s。然後用同樣的方法找出整數s的真因數之和s1。如果有s1=i,則i,s爲相親數對。
爲減少試商j循環次數,注意到數i若爲非平方數,它的大於1小於i的因數成對出現,一對中的較小因數要小於i的平方根。若數i愉爲整數t的平方,此時t爲i的一個因數,而不是一對,因而在和s中減去多加的因數t,這樣試商j循環衹要從2取到i的平方根t=SQR(i),可大減少j循環次數。縮減程序的運行時間。最後按槼格打印所找出相親數。
程序代碼如下:
#include
#include
void main()
{
int i,j,s,t,s1;
for(i=11;i
0條評論