深刻剖析C說話分化質因數的完成辦法。本站提示廣大學習愛好者：（深刻剖析C說話分化質因數的完成辦法）文章只能為提供參考，不一定能成為您想要的結果。以下是深刻剖析C說話分化質因數的完成辦法正文
起首來看一個最簡略的C說話完成質因數分化的列子：
#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++;
}
}
道理&&辦法
把一個合數分化為若干個質因數的乘積的情勢，即求質因數的進程叫做分化質因數，分化質因數只針對合數
求一個數分化質因數，要從最小的質數除起，一向除到成果為質數為止。分化質因數的算式的叫短除法，和除法的性質差不多，還可以用來求多個個數的公因式：
以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<10^9)。
輸入：
關於每組數據，輸入N的質因數的個數。
樣例輸出：
120
樣例輸入：
5
提醒：
留意：1不是N的質因數；若N為質數，N是N的質因數。
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;
}
深刻懂得
我所謂的深刻懂得，就是經由過程4星的標題來靈巧應用分化質因數的辦法，標題以下
標題2
標題描寫：
給定n，a求最年夜的k，使n！可以被a^k整除但不克不及被a^(k+1)整除。
輸出：
兩個整數n(2<=n<=1000)，a(2<=a<=1000)
輸入：
一個整數.
樣例輸出：
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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 1001
int prime[N], size;
/**
* 素數挑選法停止預處置
*/
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;
// 預處置
initProcess();
while (scanf("%d %d", &n, &a) != EOF) {
ansbase = (int *)calloc(size, sizeof(int));
ansnum = (int *)calloc(size, sizeof(int));
// 將a分化質因數
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
****************************************************************/
約數個數定理
關於一個年夜於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<=1000)
接上去的1行包含N個整數，個中每一個數的規模為(1<=Num<=1000000000)
當N=0時輸出停止。
輸入：
能夠有多組輸出數據，關於每組輸出數據，
輸入N行，個中每行對應下面的一個數的約數的個數。
樣例輸出：
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
****************************************************************/
