笔试面试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==0number==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

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

原文链接

赏

感谢支持

支付宝

微信