例5 分解質因數 題目描述 將一個正整數分解質因數。例如：輸入90，輸出 90=2*3*3*5。 輸入 輸入數據包含多行，每行是一個正整數n (1<n <100000) 。 輸出 對於每個整數n將其分解質因數。 輸入樣例 90 256 199 輸出樣例 90=2*3*3*5 256=2*2*2*2* ...
例5 分解質因數
題目描述
將一個正整數分解質因數。例如：輸入90，輸出 90=2*3*3*5。
輸入
輸入數據包含多行，每行是一個正整數n (1<n <100000) 。
輸出
對於每個整數n將其分解質因數。
輸入樣例
90
256
199
輸出樣例
90=2*3*3*5
256=2*2*2*2*2*2*2*2
199=199
（1）編程思路。
對整數n進行分解質因數，應讓變數i等於最小的質數2，然後按下述步驟完成：
1）如果i恰等於n，則說明分解質因數的過程已經結束，輸出即可。
2）如果n<>i，但n能被i整除，則應輸出i的值，並用n除以i的商，作為新的正整數n，轉第1）步。
3）如果n不能被i整除，則用i+1作為新的i值，轉第1）步。
因此，程式主體是一個迴圈，在迴圈中根據n能否整除i，進行兩種不同處理，描述為：
i=2;
while(i<n)
{
if(n%i==0)
{
printf("%d*",i) // i是n的因數，輸出i
n=n/i; // 對除以因數後的商在進行分解
}
else
i++; // 找下一個因數
}
（2）源程式。
#include <stdio.h>
int main()
{
int n,i;
while (scanf("%d",&n)!=EOF)
{
printf("%d=",n);
i=2;
while(i<n)
{
if(n%i==0)
{
printf("%d*",i);
n=n/i;
}
else
i++;
}
printf("%d\n",n);
}
return 0;
}
習題5
5-1 完全數
題目描述
完全數（Perfect number）又稱完美數或完備數，是一些特殊的自然數。它所有的真因數（即除了自身以外的約數）的和，恰好等於它本身。
例如：第一個完全數是6，它有約數1、2、3、6，除去它本身6外，其餘3個數相加，1+2+3=6。第二個完全數是28，它有約數1、2、4、7、14、28，除去它本身28外，其餘5個數相加，1+2+4+7+14=28。
編寫一個程式，求兩個正整數之間完全數的個數。
輸入
輸入數據包含多行，第一行是一個正整數n，表示測試實例的個數，然後就是n個測試實例，每個實例占一行，由兩個正整數num1和num2組成,(1<num1,num2<10000) 。
輸出
對於每組測試數據，請輸出num1和num2之間（包括num1和num2）存在的完全數個數。
輸入樣例
2
2 5
5 7
輸出樣例
0
1
（1）編程思路。
要求num1和num2之間的所有完全數，需要對num1~num2範圍內的每一個數n，計算n的所有真因數之和s，若n==s，則n就是一個完全數。框架描述為：
for(n=num1;n<=num2;n++)
{
計算n的真因數之和s ；
if(s==n)
是完全數，計數；
}
為計算n的所有真因數之和s，可令s初值為1（1是n的真因數），然後用2~n-1範圍內的每個i去除n，如果n能被i整除（即n%i==0），則i是n的真因數，s=s+i。
實際上，i（i>1）是n的真因數，則n/i也是n的真因數。因此，可以將i的範圍縮小為2~sqrt(n)。這樣，計算n的真因數之和s的操作描述為：
s=1; // s為n的真因數之和
for(i=2;i<=sqrt(n);i++) // 求解真因數之和
if(n%i==0)
if (i!=n/i) s=s+i+n/i;
else s=s+i;
因此，程式可以寫成一個嵌套的二重迴圈。
（2）源程式。
#include <stdio.h>
#include <math.h>
int main()
{
int t,num1,num2,i,n,s,cnt;
scanf("%d",&t);
while (t--)
{
scanf("%d%d",&num1,&num2);
cnt=0;
if (num1>num2) { n=num1; num1=num2; num2=n;}
for(n=num1;n<=num2;n++)
{
s=1; // s為n的真因數之和
for(i=2;i<=sqrt(n);i++) // 求解真因數之和
if(n%i==0)
{
if (i!=n/i) s=s+i+n/i;
else s=s+i;
}
if(s==n) cnt++;
}
printf("%d\n",cnt);
}
return 0;
}
5-2 親和數
題目描述
遙遠的古代，人們發現某些自然數之間有特殊的關係：如果兩個數a和b（a不等於b），a的所有真因數之和等於b，b的所有真因數之和等於a，則稱a、b是一對親和數。
例如220和284，1184和1210，2620和2924，5020和5564，6232和6368。
給定一個正整數 S（6≤S≤18000） ，找出a，b兩數中至少有一個不小於S的第一對“親和數” 。
輸入格式
一行一個整數S。
輸出格式
一行兩個整數A 和 B（用空格隔開）。A 表示第一個不小於 S 的有“親和數”的整數，B是A的“親和數”。
輸入樣例 #1
206
輸出樣例 #1
220 284
輸入樣例 #2
260
輸出樣例 #2
284 220
（1）編程思路。
程式對輸入整數begin開始的自然數進行窮舉，演算法描述為：
for(n=begin；；n++)
{
計算n的真因數之和 s ；
if （s==n） continue；
計算s的真因數之和 m ；
if(m==n) // 如果兩數相等，是解
{
輸出解的情況；
}
}
計算自然數的真因數之和的方法，可以參見前面的習題5-1“完全數”。
（2）源程式。
#include <stdio.h>
#include <math.h>
int main()
{
int begin,i,n,s,m,k;
scanf("%d",&begin);
for(n=begin;;n++)
{
s=1; // s為n的真因數之和
k=1; // k為n的真因數個數
for(i=2;i<=(int)sqrt(1.0*n);i++) // 求解真因數之和
if(n%i==0)
{
s=s+i+n/i;
k+=2;
}
i--;
if (i*i==n) s-=i;
if(k==1 || s==n) // 若n為質數或完數，進行下次迴圈
continue;
m=1; // m為s的真因數之和
for(i=2;i<=(int)sqrt(1.0*s);i++)
if(s%i==0)
m+=i+s/i; // 計算s的真因數之和
i--;
if (i*i==s) m-=i;
if(m==n) // 如果兩數相等，輸出親和數
{
printf("%d %d\n",n,s);
break;
}
}
return 0;
}
5-3 The number of divisors about Humble Numbers
Problem Description
A number whose only prime factors are 2,3,5 or 7 is called a humble number. The sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, ... shows the first 20 humble numbers.
Now given a humble number, please write a program to calculate the number of divisors about this humble number.For examle, 4 is a humble,and it have 3 divisors(1,2,4);12 have 6 divisors.
Input
The input consists of multiple test cases. Each test case consists of one humble number n,and n is in the range of 64-bits signed integer. Input is terminated by a value of zero for n.
Output
For each test case, output its divisor number, one line per case.
Sample Input
4
12
0
Sample Output
3
6
（1）編程思路。
若一個大於1正整數n可以分解質因數：n=(p1^a1)*(p2^a2)*(p3^a3)*…*(pk^ak),
則由約數個數定理可知n的正約數有 (a1+1)(a2+1)(a3+1)…(ak+1)個。
本題要求一個給定醜數n的約數個數，而一個醜數分解質因數後，其質因數只有2、3、5或7這4個，因此只需求出n中分別含有質因數2、3、5和7的個數即可。
（2）源程式。
#include <stdio.h>
int fun(__int64 n,int x) // 求整數n分解質因數後含質因數x的個數
{ int sum=0;
while(n%x==0)
{
sum++;
n/=x;
}
return sum;
}
int main()
{
int cnt1,cnt2,cnt3,cnt4;
__int64 n;
while(scanf("%I64d",&n) && n!=0)
{
cnt1=cnt2=cnt3=cnt4=1;
cnt1+=fun(n,2);
cnt2+=fun(n,3);
cnt3+=fun(n,5);
cnt4+=fun(n,7);
printf("%d\n",cnt1*cnt2*cnt3*cnt4);
}
return 0;
}
