笔试面试3 将一个数分解成质因数的形式以及如何判断一个数是否是质数 - c++编程基础

虽说已经找到了实习，offer也拿了，但是还是决定多上来刷刷一些简单的，很水的笔试面试题。

这些题仅适合学渣级的算法菜鸟学习，ACM的大神们请自动略过。

将一个数分解成质因数的形式，例如：

10=2*5 100=2*2*5*5

其实这道题的实现很简单。设一个i初始值为2，然后用该数一直除，递增i即可。

以下是实现：

#include 
  
   
#include 
   
     int main() { while(true){ printf( 请输入数字: ); int number; scanf(%d,&number); if(number<0){//考虑输入不合法 printf(输入不合法(<0)); continue; } if(number==0||number==1){//考虑输入的是0或者1 printf(%d=%d,number,number); continue; } int i=2; printf(%d=,number); while(number>=i){ while(number%i==0){ //一直除i,直到不能整除时，i+1 printf(%d,i); if(number!=i) printf(*); number=number/i; } i++; } } getch(); }

测试图：

如何判断一个数是否是质数。

这个就更简单了。

直接上源码：

#include 
  
   
#include 
   
     #define TRUE 1 #define FALSE -1 int isPrime(int number){//c 没有bool类型... if(number<=1){//考虑输入不合法 printf(输入不合法(<2) ); return FALSE; } if(number==2) return TRUE; int i=2; while(i<=number){ while(number%i==0){ if(i==number) return TRUE; else return FALSE; } i++; } } int main() { while(TRUE){ printf( 请输入数字: ); int number; scanf(%d,&number); if(isPrime(number)==TRUE) printf(%d is a prime number! ,number); else printf(%d not a prime number! ,number); } getch(); }

测试截图：

不过如果一个数比较大的时候，这个时间复杂度就会比较大，一个比较好的方法就是利用其平方根。

i的最大值只需递增到sqrt(n)即可。（原因是i*i==n时，i就是中间的那个因子）

源码：

#include 
  
   
#include 
   
     #include 
    
      #define TRUE 1 #define FALSE -1 int isPrime(int number){//c 没有bool类型... if(number<=1){//考虑输入不合法 printf(输入不合法(<2) ); return FALSE; } if(number==2) return TRUE; int i=2; int counts=1; while(i<=sqrt(number)){ if(number%i==0)//如果整除，因子数+1 counts++; i++; } if(counts==1) return TRUE; else return FALSE; } int main() { while(TRUE){ printf( 请输入数字: ); int number; scanf(%d,&number); if(isPrime(number)==TRUE) printf(%d is a prime number! ,number); else printf(%d not a prime number! ,number); } getch(); }

测试图：