将一个正整数分解质因数。例如:输入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要特别处理。
待续未完。相信还有更好的算法。