笔试面试3将一个数分解成质因数的形式以及如何判断一个数是否是质数


笔试面试3将一个数分解成质因数的形式以及如何判断一个数是否是质数

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

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


将一个数分解成质因数的形式,例如:

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

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

以下是实现:

#include <stdio.h>
#include <conio.h>
int main()
{
 	while(true){
		printf("\n请输入数字:\n");
		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 <stdio.h>
#include <conio.h>
#define TRUE  1
#define FALSE -1
int isPrime(int number){//c 没有bool类型... 
	 if(number<=1){//考虑输入不合法 
		    printf("输入不合法(<2)\n"); 
		    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("\n请输入数字:\n");
		int number;
    	scanf("%d",&number);
    	if(isPrime(number)==TRUE)
		   printf("%d is a prime number!\n",number);
	    else
   		   printf("%d not a prime number!\n",number); 		
    }
    getch();
}

测试截图:


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

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

源码:

#include <stdio.h>
#include <conio.h>
#include <math.h>
#define TRUE  1
#define FALSE -1
int isPrime(int number){//c 没有bool类型... 
	 if(number<=1){//考虑输入不合法 
		    printf("输入不合法(<2)\n"); 
		    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("\n请输入数字:\n");
		int number;
    	scanf("%d",&number);
    	if(isPrime(number)==TRUE)
		   printf("%d is a prime number!\n",number);
	    else
   		   printf("%d not a prime number!\n",number); 		
    }
    getch();
}

测试图:


——————————————————————————————————————————————————————————————————

//写的错误或者不好的地方请多多指导,可以在下面留言或者点击左上方邮件地址给我发邮件,指出我的错误以及不足,以便我修改,更好的分享给大家,谢谢。

转载请注明出处:http://blog.csdn.net/qq844352155

author:天下无双

Email:coderguang@gmail.com

2014-11-5

于GDUT

——————————————————————————————————————————————————————————————————


发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注