Question

C语言中素数判断

Answer 1

★试除法　　首先要介绍的，当然非"试除法"莫属啦。考虑到有些读者是菜鸟，稍微解释一下。
　　"试除"，顾名思义，就是不断地尝试能否整除。比如要判断自然数
x
是否质数，就不断尝试小于
x
且大于1的自然数，只要有一个能整除，则
x
是合数；否则，x
是质数。
　　显然，试除法是最容易想到的思路。不客气地说，也是最平庸的思路。不过捏，这个最平庸的思路，居然也有好多种境界。大伙儿请看：
◇境界1　　在试除法中，最最土的做法，就是：
　　假设要判断
x
是否为质数，就从
2
一直尝试到
x-1。这种做法，其效率应该是最差的。如果这道题目有10分，按照这种方式做出的代码，即便正确无误，俺也只给1分。
◇境界2　　稍微聪明一点点的程序猿，会想：x
如果有（除了自身以外的）质因数，那肯定会小于等于
x/2，所以捏，他们就从
2
一直尝试到
x/2
即可。
　　这一下子就少了一半的工作量哦，但依然是很笨的办法。打分的话，即便代码正确也只有2分
◇境界3　　再稍微聪明一点的程序猿，会想了：除了2以外，所有可能的质因数都是奇数。所以，他们就先尝试
2，然后再尝试从
3
开始一直到
x/2
的所有奇数。
　　这一下子，工作量又少了一半哦。但是，俺不得不说，依然很土。就算代码完全正确也只能得3分。
◇境界4　　比前3种程序猿更聪明的，就会发现：其实只要从
2
一直尝试到√x，就可以了。估计有些网友想不通了，为什么只要到√x
即可？
　　简单解释一下：因数都是成对出现的。比如，100的因数有：1和100，2和50，4和25，5和20，10和10。看出来没有？成对的因数，其中一个必然小于等于100的开平方，另一个大于等于100的开平方。至于严密的数学证明，用小学数学知识就可以搞定，俺就不啰嗦了。
◇境界5　　那么，如果先尝试2，然后再针对
3
到√x
的所有奇数进行试除，是不是就足够优了捏？答案显然是否定的嘛？写到这里，才刚开始热身哦。
　　一些更加聪明的程序猿，会发现一个问题：尝试从
3
到√x
的所有奇数，还是有些浪费。比如要判断101是否质数，101的根号取整后是10，那么，按照境界4，需要尝试的奇数分别是：3，5，7，9。但是你发现没有，对9的尝试是多余的。不能被3整除，必然不能被9整除......顺着这个思路走下去，这些程序猿就会发现：其实，只要尝试小于√x的
质数
即可。而这些质数，恰好前面已经算出来了（是不是觉得很妙？）。

希望采纳

Answer 2

代码如下：

#include
<stdio.h>
#include
<conio.h>
void
main()
{
long
m,n=2;
double
l;
printf("please
input
an
number:
\n");
scanf("%d",&m);
for(n=2;n<=m;n++)
//这里设置n<=m，是要将2到输入值之间所有的数拿来整除m
{
l=m%n;
if(l==0)
//这里，得到余数为0的时候
break;
//跳出循环
}
if(n<m)
//如果被除数n小于输入值m，那么m肯定有除了1和本身外别的约数，所以下面不是素数
printf("不是素数\n");
else
//另外的，如果n不小于m，那只有可能等于m，那么m就不会有别的约数
printf("是素数\n");
getch();
}

首先要清楚什么是素数，素数就是只能被1和自己整除的数字，那么：

我的思路是，首先定义一个变量m存储你输入的数值，然后，从2开始到m依次去作为m的除数，如果在这个过程中有一个数字L能整除m，那么跳出循环，跳出之后判断L是否等于m，如果不等于，那么不是素数，如果相等那么是素数

Answer 3

Answer 4

Answer 5

素数就是只能被1和它本身整除的数，
技巧嘛，那就是所有的偶数都不是素数，所以判定的时候用
for(i=3;i<=100;i+=2)直接判断奇数就好、
比如100以内的素数C程序，
#include<stdio.h>
main()
{
int
i,k;

for(i=3;i<=100;i+=2)

{

for(k=2;k<i;k++)

if(i%k==0)

break;

else

{printf("%d
",i);

break;}

}
}