或者说计算机相关专业的大一新生在开始学习编程时会接触到的一个问题就是判断素数。下面这篇文章主要介绍C语言中判断素数(求素数)的思路和方法,有需要的朋友可以参考一下。
目录
前言思路1实现:思路2实现:《C与指针》 4.14-2:补充:素数四种判定方法的实例总结
前言
也称为质数。所谓质数,是指除了1和它本身之外,不能被任何整数整除的数。例如,17是一个质数,因为它不能被2到16之间的任何整数整除。
1)思路:因此,判断一个整数M是否为素数,只要将M除以2到M-1之间的每一个整数即可。如果它们都不能被整除,那么M就是一个素数。
2):判断方法也可以简化。m不一定要被2到m-1之间的每一个整数去除,只需要被2到1之间的每一个整数去除。如果m不能被2和2之间的任何整数整除,则m一定是素数。比如判断17是不是质数,只需要用2到4之间的每一个整数除17就可以了。由于它们都不能被整除,所以可以确定17是一个质数。
原因:因为如果m能被2到m-1之间的任意整数整除,那么它的两个因子中一定有一个小于等于,另一个大于等于。比如16能被2、4、8整除,16=2*8,2小于4,8大于4,16=4*4,4=16,那么只需要确定2和4之间是否有因子。
思路1实现:
#包含stdio.h
int main() {
int n;
Printf('请输入1到100之间的整数:\ n ');
scanf('%d ',n);
int m=0;
for(int I=2;I n;i ) {
if(n % i==0) {
m;
}
}
if (m==0) {
Printf('%d是质数\n ',n);
}否则{
Printf('%d不是质数\n ',n);
}
返回0;
}
思路2实现:
#包含stdio.h
#包含数学. h
int main() {
int n;
Printf('请输入1到100之间的整数:\ n ');
scanf('%d ',n);
int I=0;
int q=sqrt(n);
for(I=2;I=q;i ) {
if(n % i==0) {
打破;
}
}
if (i q) {
Printf('%d是质数\n ',n);
}否则{
Printf('%d不是质数\n ',n);
}
返回0;
}
《C与指针》4.14 - 2:
打印1到100之间的所有质数:
#包含stdio.h
int main() {
int num,除数;
printf('1,2 ');
for(num=3;num=100num=2) {
for(除数=3;除数;除数=2 ) {
if (num %除数==0) {
打破;
}
}
if(除数=数字){
printf(',%d ',num);
}
}
printf(' \ n ');
返回0;
}
结果:
1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
补充:判断素数的4种方法实例
# includestdio.h
#包含math.h
//方法一:从1-n逐一判断;
bool isPrimel_1(int n)
{ for(int I=2;在;我)
如果(n%i==0)
返回false
返回true
}
//方法二:规定判断数n为判断结束的条件,
//因为根号后的数是n的最大因子,所以最大因子后的数对判断该数是否质数没有意义。
bool isPrimel_2(int n)
{ for(int I=2;isqrt(n);我)
如果(n%i==0)
返回false
返回true
}
//方法三:你只需要判断一半的数字。如果超过自身的一半,
//补数的结果永远不会是0,除非是这个数对这个数的补数。
bool isPrimel_3(int n)
{ int I;
如果(n%2==0)
返回0;
for(I=3;I=n/2;i=2){
如果(n%i==0)
返回0;
返回1;
}
}
//方法四:从3-n,只判断奇数,先判断一个数的奇偶性。如果是奇数,
//只计算奇数从3到自身的余数。同样,如果是偶数,一定不是素数。
bool isPrimel_4(int n)
{ int i,j=1;
如果(n%2==0)
返回0;
否则{
for(I=3;I=n;I=I ^ 2){
如果(n%i==0)
j=I;
打破;
}
}
如果(j==n)
返回0;
返回1;
}
int main()
{
int n;
Printf('请输入一个数字:');
scanf('%d ',n);
printf('%d,%d,%d,%d\n ',isPrimel_1(n),isPrimel_2(n),isPrimel_3(n),isPrimel _ 4(n));
返回0;
}
总结
这篇关于C语言判断质数的文章到此为止。关于C语言判断素数的更多信息,请搜索我们之前的文章或者继续浏览下面的相关文章。希望大家以后能多多支持我们!
郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。