笔试面试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
——————————————————————————————————————————————————————————————————