C語言的開發在日常開發中被廣泛使用,而我們都知道C語言是簡單的編譯方法,愛站技術頻道小編今天就為大家帶來了C語言開發中分解質因數的操作執行個體,一起去進入下文看看吧!
首先來看一個最簡單的C語言實作質因數分解的列子:
#include void main( )
{
int data, i = 2;
scanf("%d", &data);
while(data > 1)
{
if(data % i == 0)
{
printf("%d ", i);
data /= i;
}
else i++;
}
}
原理&&方法
把一個合數分解為若幹個質因數的乘積的形式,即求質因數的過程叫做分解質因數,分解質因數隻針對合數
求一個數分解質因數,要從最小的質數除起,一直除到結果為質數為止。分解質因數的算式的叫短除法,和除法的性質差不多,還可以用來求多個個數的公因式:
以24為例:
2 -- 24
2 -- 12
2 -- 6
3 (3是質數,結束)
得出 24 = 2 × 2 × 2 × 3 = 2^3 * 3
代碼
可先用素數篩選法,篩選出符合條件的質因數,然後for循環周遊即可,通過一道題目來show一下這部分代碼
題目1
題目描述:
求正整數N(N>1)的質因數的個數。
相同的質因數需要重複計算。如120=2*2*2*3*5,共有5個質因數。
輸入:
可能有多組測試資料,每組測試資料的輸入是一個正整數N,(1 輸出:
對于每組資料,輸出N的質因數的個數。
樣例輸入:
120
樣例輸出:
5
提示:
注意:1不是N的質因數;若N為質數,N是N的質因數。
ac代碼
#include int main()
{
int n, count, i;
while (scanf("%d", &n) != EOF) {
count = 0;
for (i = 2; i * i 1) {
count ++;
}
printf("%d\n", count);
}
return 0;
}
深入了解
我所謂的深入了解,就是通過4星的題目來靈活運用分解質因數的方法,題目如下
題目2
題目描述:
給定n,a求最大的k,使n!可以被a^k整除但不能被a^(k+1)整除。
輸入:
兩個整數n(2 輸出:
一個整數.
樣例輸入:
6 10
樣例輸出:
1
思路
a^k和n!都可能非常大,甚至超過long long int的表示範圍,是以也就不能直接用取餘操作判斷它們之間是否存在整除關系,是以我們需要換一種思路,從分解質因數入手,假設兩個數a和b:
a = p1^e1 * p2^e2 * ... * pn^en, b = p1^d1 * p2^d2 * ... * pn^dn
, 則b除以a可以表示為:
b / a = (p1^d1 * p2^d2 * ... * pn^dn) / (p1^e1 * p2^e2 * ... * pn^en)
若b能被a整除,則 b / a必為整數,且兩個素數必護質,則我們可以得出如下規律:
若a存在質因數px,則b必也存在該質因數,且該素因數在b中對應的幂指數必不小于在a中的幂指數
另b = n!, a^k = p1^ke1 * p2^ke2 * ... * pn^ken,是以我們需要确定最大的非負整數k即可。要求得該k,我們隻需要依次測試a中每一個素因數,确定b中該素因數是a中該素因數的幂指數的多少倍即可,所有倍數中最小的那個即為我們要求得的k
分析到這裡,剩下的工作似乎隻是對a和n!分解質因數,但是将n!計算出來再分解質因數,這樣n!數值太大。考慮n!中含有素因數p的個數,即确定素因數p對應的幂指數。我們知道n!包含了從1到n區間所有整數的乘積, 這些乘積中每一個p的倍數(包括其本身)都對n!貢獻至少一個p因子,且我們知道在1到n中p的倍數共有n/p個。同理,計算p^2,p^3,...即可
代碼
#include #include #include #define N 1001
int prime[N], size;
void initProcess()
{
int i, j;
for (prime[0] = prime[1] = 0, i = 2; i
約數個數定理
對于一個大于1的正整數n可以分解質因數:
n = p1^a1 * p2^a2 * p3^a3 * ... * pn^an
, 則n的正約數的個數為:
(a1 + 1) * (a2 + 1) * ... *(an + 1)
.其中p1,p2,..pn都是n的質因數,a1, a2...an是p1,p2,..pn的指數
證明
n可以分解質因數:n=p1^a1 * p2^a2 * p3^a3 * … * pk^ak,
由約數定義可知p1^a1的約數有:p1^0, p1^1, p1^2......p1^a1 ,共(a1+1)個;同理p2^a2的約數有(a2+1)個......pk^ak的約數有(ak+1)個
故根據乘法原理:n的約數的個數就是
(a1+1)*(a2+1)*(a3+1)*…* (ak+1)
題目3
題目描述:
輸入n個整數,依次輸出每個數的約數的個數
輸入:
輸入的第一行為N,即數組的個數(N 接下來的1行包括N個整數,其中每個數的範圍為(1 當N=0時輸入結束。
輸出:
可能有多組輸入資料,對于每組輸入資料,
輸出N行,其中每一行對應上面的一個數的約數的個數。
樣例輸入:
5
1 3 4 6 12
樣例輸出:
1
2
3
4
6
代碼
#include #include #define N 40000
typedef long long int lint;
int prime[N], size;
void init()
{
int i, j;
for (prime[0] = prime[1] = 0, i = 2; i
以上就是愛站技術頻道小編介紹的C語言開發中分解質因數的操作執行個體,相信大家在看完後對開發有很大的幫助,如果你也覺得js.aizhan.com,要記得繼續支援我們哦。