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要特别处理。

待续未完。相信还有更好的算法。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wywzdj.html