首先來(lái)看一個(gè)最簡(jiǎn)單的C語(yǔ)言實(shí)現(xiàn)質(zhì)因數(shù)分解的列子：
#include <stdio.h>void main( ){ int data, i = 2; scanf("%d", &data); while(data > 1) { if(data % i == 0) { printf("%d ", i); data /= i; } else i++; }}原理&&方法
把一個(gè)合數(shù)分解為若干個(gè)質(zhì)因數(shù)的乘積的形式，即求質(zhì)因數(shù)的過(guò)程叫做分解質(zhì)因數(shù)，分解質(zhì)因數(shù)只針對(duì)合數(shù)
求一個(gè)數(shù)分解質(zhì)因數(shù)，要從最小的質(zhì)數(shù)除起，一直除到結(jié)果為質(zhì)數(shù)為止。分解質(zhì)因數(shù)的算式的叫短除法，和除法的性質(zhì)差不多，還可以用來(lái)求多個(gè)個(gè)數(shù)的公因式：
以24為例：
2 -- 24
2 -- 12
2 -- 6
3 （3是質(zhì)數(shù)，結(jié)束）
得出 24 = 2 × 2 × 2 × 3 = 2^3 * 3
代碼
可先用素?cái)?shù)篩選法，篩選出符合條件的質(zhì)因數(shù)，然后for循環(huán)遍歷即可，通過(guò)一道題目來(lái)show一下這部分代碼
題目1
題目描述：
求正整數(shù)N(N>1)的質(zhì)因數(shù)的個(gè)數(shù)。
相同的質(zhì)因數(shù)需要重復(fù)計(jì)算。如120=2*2*2*3*5，共有5個(gè)質(zhì)因數(shù)。
輸入：
可能有多組測(cè)試數(shù)據(jù)，每組測(cè)試數(shù)據(jù)的輸入是一個(gè)正整數(shù)N，(1<N<10^9)。
輸出：
對(duì)于每組數(shù)據(jù)，輸出N的質(zhì)因數(shù)的個(gè)數(shù)。
樣例輸入：
120
樣例輸出：
5
提示：
注意：1不是N的質(zhì)因數(shù)；若N為質(zhì)數(shù)，N是N的質(zhì)因數(shù)。
ac代碼
#include <stdio.h> int main() { int n, count, i; while (scanf("%d", &n) != EOF) { count = 0; for (i = 2; i * i <= n; i ++) { if(n % i == 0) { while (n % i == 0) { count ++; n /= i; } } } if (n > 1) { count ++; } printf("%d/n", count); } return 0; } 深入理解
我所謂的深入理解，就是通過(guò)4星的題目來(lái)靈活運(yùn)用分解質(zhì)因數(shù)的方法，題目如下
題目2
題目描述：
給定n，a求最大的k，使n！可以被a^k整除但不能被a^(k+1)整除。
輸入：
兩個(gè)整數(shù)n(2<=n<=1000)，a(2<=a<=1000)
輸出：
一個(gè)整數(shù).
樣例輸入：
6 10
樣例輸出：
1
思路
a^k和n!都可能非常大，甚至超過(guò)long long int的表示范圍，所以也就不能直接用取余操作判斷它們之間是否存在整除關(guān)系，因此我們需要換一種思路，從分解質(zhì)因數(shù)入手，假設(shè)兩個(gè)數(shù)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必為整數(shù)，且兩個(gè)素?cái)?shù)必護(hù)質(zhì)，則我們可以得出如下規(guī)律：
若a存在質(zhì)因數(shù)px，則b必也存在該質(zhì)因數(shù)，且該素因數(shù)在b中對(duì)應(yīng)的冪指數(shù)必不小于在a中的冪指數(shù)
另b = n!, a^k = p1^ke1 * p2^ke2 * ... * pn^ken，因此我們需要確定最大的非負(fù)整數(shù)k即可。要求得該k，我們只需要依次測(cè)試a中每一個(gè)素因數(shù)，確定b中該素因數(shù)是a中該素因數(shù)的冪指數(shù)的多少倍即可，所有倍數(shù)中最小的那個(gè)即為我們要求得的k
分析到這里，剩下的工作似乎只是對(duì)a和n!分解質(zhì)因數(shù)，但是將n!計(jì)算出來(lái)再分解質(zhì)因數(shù)，這樣n!數(shù)值太大?？紤]n!中含有素因數(shù)p的個(gè)數(shù)，即確定素因數(shù)p對(duì)應(yīng)的冪指數(shù)。我們知道n!包含了從1到n區(qū)間所有整數(shù)的乘積， 這些乘積中每一個(gè)p的倍數(shù)（包括其本身）都對(duì)n!貢獻(xiàn)至少一個(gè)p因子，且我們知道在1到n中p的倍數(shù)共有n/p個(gè)。同理，計(jì)算p^2，p^3,...即可
代碼
#include <stdio.h> #include <stdlib.h> #include <string.h> #define N 1001 int prime[N], size; /** * 素?cái)?shù)篩選法進(jìn)行預(yù)處理 */ void initProcess() { int i, j; for (prime[0] = prime[1] = 0, i = 2; i < N; i ++) { prime[i] = 1; } size = 0; for (i = 2; i < N; i ++) { if (prime[i]) { size ++; for (j = 2 * i; j < N; j += i) { prime[j] = 0; } } } } int main(void) { int i, n, a, k, num, count, base, tmp, *ansbase, *ansnum; // 預(yù)處理 initProcess(); while (scanf("%d %d", &n, &a) != EOF) { ansbase = (int *)calloc(size, sizeof(int)); ansnum = (int *)calloc(size, sizeof(int)); // 將a分解質(zhì)因數(shù) for (i = 2, num = 0; i < N && a != 1; i ++) { if (prime[i] && a % i == 0) { ansbase[num] = i; ansnum[num] = 0; while (a != 1 && a % i == 0) { ansnum[num] += 1; a = a / i; } num ++; } } // 求最小的k for (i = 0, k = 0x7fffffff; i < num; i ++) { base = ansbase[i]; count = 0; while (base <= n) { count += n / base; base *= ansbase[i]; } tmp = count / ansnum[i]; if (tmp < k) k = tmp; } printf("%d/n", k); } return 0; } /************************************************************** Problem: 1104 User: wangzhengyi Language: C Result: Accepted Time:0 ms Memory:916 kb ****************************************************************/ 約數(shù)個(gè)數(shù)定理
對(duì)于一個(gè)大于1的正整數(shù)n可以分解質(zhì)因數(shù)：
n = p1^a1 * p2^a2 * p3^a3 * ... * pn^an
, 則n的正約數(shù)的個(gè)數(shù)為：
(a1 + 1) * (a2 + 1) * ... *(an + 1)
.其中p1,p2,..pn都是n的質(zhì)因數(shù)，a1, a2...an是p1,p2,..pn的指數(shù)
證明
n可以分解質(zhì)因數(shù)：n=p1^a1 * p2^a2 * p3^a3 * … * pk^ak,
由約數(shù)定義可知p1^a1的約數(shù)有:p1^0, p1^1, p1^2......p1^a1 ，共（a1+1）個(gè);同理p2^a2的約數(shù)有（a2+1）個(gè)......pk^ak的約數(shù)有（ak+1）個(gè)
故根據(jù)乘法原理：n的約數(shù)的個(gè)數(shù)就是
(a1+1）*（a2+1）*（a3+1）*…* (ak+1)
題目3
題目描述：
輸入n個(gè)整數(shù),依次輸出每個(gè)數(shù)的約數(shù)的個(gè)數(shù)
輸入：
輸入的第一行為N，即數(shù)組的個(gè)數(shù)(N<=1000)
接下來(lái)的1行包括N個(gè)整數(shù)，其中每個(gè)數(shù)的范圍為(1<=Num<=1000000000)
當(dāng)N=0時(shí)輸入結(jié)束。
輸出：
可能有多組輸入數(shù)據(jù)，對(duì)于每組輸入數(shù)據(jù)，
輸出N行，其中每一行對(duì)應(yīng)上面的一個(gè)數(shù)的約數(shù)的個(gè)數(shù)。
樣例輸入：
5
1 3 4 6 12
樣例輸出：
1
2
3
4
6
代碼
#include <stdio.h> #include <stdlib.h> #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 < N; i ++) { prime[i] = 1; } size = 0; for (i = 2; i < N; i ++) { if (prime[i]) { size ++; for (j = 2 * i; j < N; j += i) prime[j] = 0; } } } lint numPrime(int n) { int i, num, *ansnum, *ansprime; lint count; ansnum = (int *)malloc(sizeof(int) * (size + 1)); ansprime = (int *)malloc(sizeof(int) * (size + 1)); for (i = 2, num = 0; i < N && n != 1; i ++) { if (prime[i] && n % i == 0) { ansprime[num] = i; ansnum[num] = 0; while (n != 1 && n % i == 0) { ansnum[num] += 1; n /= i; } num ++; } } if (n != 1) { ansprime[num] = n; ansnum[num] = 1; num ++; } for (i = 0, count = 1; i < num; i ++) { count *= (ansnum[i] + 1); } free(ansnum); free(ansprime); return count; } int main(void) { int i, n, *arr; lint count; init(); while (scanf("%d", &n) != EOF && n != 0) { arr = (int *)malloc(sizeof(int) * n); for (i = 0; i < n; i ++) { scanf("%d", arr + i); } for (i = 0; i < n; i ++) { count = numPrime(arr[i]); printf("%lld/n", count); } free(arr); } return 0; } /************************************************************** Problem: 1087 User: wangzhengyi Language: C Result: Accepted Time:190 ms Memory:1068 kb ****************************************************************/ 新聞熱點(diǎn)
疑難解答
圖片精選
