C语言经典算法:如何较快的分解质因数
将一个正整数分解质因数。例如:输入90,打印出90=2*3*3*5。
初级算法:
- #include<stdio.h>
- #include<stdlib.h>
- #include<math.h>
- int main()
- {
- int n,i;
- scanf("%d",&n);
- printf("%d=",n);
- for(i=2;i<=sqrt(n);i++)
- {
- if(n%i==0)
- {
- n/=i;
- printf("%d*",i--);
- }
- }
- printf("%d\n",n);
- system("pause");
- return 0;
- }
改进版:
- #include<stdio.h>
- #include<stdlib.h>
- #include<math.h>
- int main()
- {
- int n,i;
- scanf("%d",&n);
- printf("%d=",n);
- while(n%2==0){
- printf("%d*",2);
- n/=2;
- }
- for(i=3;i<=sqrt(n);i+=2)
- {
- if(n%i==0)
- {
- n/=i;
- printf("%d*",i);
- i-=2;
- }
- }
- printf("%d\n",n);
- system("pause");
- return 0;
- }
因为在所以的质数中只有2是偶数外,其他的质数都是奇数。所以i可以一次+2跳过所有的偶数。不过2要特别处理。
待续未完。相信还有更好的算法。
相关推荐
IT之家 2020-03-11
graseed 2020-10-28
zbkyumlei 2020-10-12
SXIAOYI 2020-09-16
jinhao 2020-09-07
impress 2020-08-26
liuqipao 2020-07-07
淡风wisdon大大 2020-06-06
yoohsummer 2020-06-01
chenjia00 2020-05-29
baike 2020-05-19
扭来不叫牛奶 2020-05-08
hxmilyy 2020-05-11
黎豆子 2020-05-07
xiongweiwei00 2020-04-29
Cypress 2020-04-25
冰蝶 2020-04-20