深入分析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
题目1 题目描述：
#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("%dn",count);
}
return 0;
}
深入理解 题目2 题目描述： 思路 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中的幂指数
分析到这里，剩下的工作似乎只是对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,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("%dn",k);
}
return 0;
}
/**************************************************************
Problem: 1104
User: wangzhengyi
Language: C
Result: Accepted
Time:0 ms
Memory:916 kb
****************************************************************/
约数个数定理 n = p1^a1 * p2^a2 * p3^a3 * ... * pn^an ,则n的正约数的个数为： (a1 + 1) * (a2 + 1) * ... *(an + 1) .其中p1,p2,..pn都是n的质因数，a1,a2...an是p1,..pn的指数 证明 由约数定义可知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 题目描述：
#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,*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,*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("%lldn",count);
}
free(arr);
}
return 0;
}
/**************************************************************
Problem: 1087
User: wangzhengyi
Language: C
Result: Accepted
Time:190 ms
Memory:1068 kb
****************************************************************/
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |