1到1000素数c语言程序（100到200素数c语言程序） - 原点资讯

题目

问：1-100之间有多少个素数，并输出所有素数及素数的个数。

这个题面就很容易理解了，数学上对素数的定义是这样的：质数又称素数，指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。

换句话说，只有两个正因数（1和自己）的自然数即为素数。比1大但不是素数的数称为合数。并且1和0既非素数也非合数。

1到1000素数c语言程序,100到200素数c语言程序(1)

好了，数学上素数是这样定义，我们应该把它用计算机的语言表示出来呀。

这里我们就用一种最简单的方式来表示：

编程思想：

一个数n，要判断它是不是素数，直接用n除以2到n里面所有的数，如果有一个能整除，则这个数n不是素数。如果都不能被整除，则这个数是素数。

上面这句话用代码写出来是这样的：

for(j = 2; j<= n; j ) //能被2到n整除的数
{
if(i % j == 0) //取余判断
{
flag = 0;
break;
//只要有一个被整除，则跳出循环
}
}

1到1000素数c语言程序,100到200素数c语言程序(2)

到这里，我们仔细想想，有必要一直除到n去吗？答案是没有必要的，来看一个例子。

比如判断17是不是素数，我们其实只需要计算：

17%2
17%3
17%4

只需要计算以上三个式子，我们就可以断定，17是一个素数。

为什么呢？因为数学知识告诉我们：任何一个数都不可能分解成两个大于其平方根的数的乘积呀，肯定只能分解为一个大于或等于其平方根，另一个小于或等于其平方根的两个数相乘。

我们知道，17开根号的值是一个4到5之间的数，取int之后就是4，既然我们已经从2一直取余取到了4都没有一个可以整除，那么就没有必要继续计算下去了，因为接下来的数也肯定不能被整除。

我们吧代码优化一下：

for(j = 2; j<= sqrt(n); j ) //能被2到n的开方根整除的数
{
if(i % j == 0)
{
flag = 0;
break;
}
}

好了，这样子你能明显感受到我们一下子减少了很多计算量，时间复杂度降低了。

1到1000素数c语言程序,100到200素数c语言程序(3)

完整代码

以上是知道一个数，判断它是不是素数，这里我们要做的是输出1-100内所有的素数，那么就要有一个双重for循环，一个数一个数地去判断，然后输出素数。

这里给出完整代码：

//输出1-100的所有素数
void Prime()
{
int i,j,flag,n;
n = 100; //100以内的素数
flag = 1; //标识变量，是素数则为1
for(i = 2; i <= 100; i ) //从2开始，遍历到100
{
flag = 1;
for(j = 2; j*j <= i; j ) //能被2 - sqrt(i)整除的数
{
if(i % j == 0)
{
flag = 0;
break;
}
}
if(flag == 1)
printf("%d ",i); //输出素数
}
}