C语言经典算法:如何较快的分解质因数

将一个正整数分解质因数。例如:输入90,打印出90=2*3*3*5。

初级算法:

  1. #include<stdio.h>   
  2. #include<stdlib.h>   
  3. #include<math.h>   
  4. int main()  
  5. {  
  6.         int n,i;  
  7.         scanf("%d",&n);  
  8.         printf("%d=",n);  
  9.         for(i=2;i<=sqrt(n);i++)  
  10.         {  
  11.            if(n%i==0)  
  12.            {  
  13.               n/=i;  
  14.               printf("%d*",i--);  
  15.        }  
  16.          }  
  17.        printf("%d\n",n);  
  18.         system("pause");  
  19.         return 0;  

C语言经典算法:如何较快的分解质因数

改进版:

  1. #include<stdio.h>   
  2. #include<stdlib.h>   
  3. #include<math.h>   
  4. int main()  
  5. {  
  6.         int n,i;  
  7.         scanf("%d",&n);  
  8.         printf("%d=",n);  
  9.         while(n%2==0){  
  10.                                     printf("%d*",2);  
  11.                                     n/=2;  
  12.                                     }  
  13.         for(i=3;i<=sqrt(n);i+=2)  
  14.         {  
  15.            if(n%i==0)  
  16.            {  
  17.               n/=i;  
  18.               printf("%d*",i);  
  19.               i-=2;  
  20.        }  
  21.          }  
  22.        printf("%d\n",n);  
  23.            
  24.         system("pause");  
  25.         return 0;  
  26. }  

因为在所以的质数中只有2是偶数外,其他的质数都是奇数。所以i可以一次+2跳过所有的偶数。不过2要特别处理。

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

 

 

 

 

 

相关推荐