Question

C语言：利用int prime（int n）函数，实现输出100~300之间所有素数。

#include<stdio.h>
#include<math.h>
int prime(int n)
{
int i;
for(i=2;i<sqrt(n);i++) /*循环除去sqrt(n)以下的数*/
{
if(n%i==0)
return(0);/*如果不是素数,返回0*/
}
return 1;/*如果是素数,返回1*/
}

main(void)
{
int i;
for(i=100;i<=300;i++)
{
if(prime(i))
printf("%d ",i);
}
getchar();
}

————

上面的程序 for(i=2;i<sqrt(n);i++) /*循环除去sqrt(n)以下的数*/
{
if(n%i==0)
return(0);/*如果不是素数,返回0*/
}
return 1;/*如果是素数,返回1*/
这一块我没看懂。。。求大神解释，谢谢

Answer 1

1. 素数就是一个大于1的自然数，除了1和它本身外，不能被其他自然数整除

#include <stdio.h>

int IsPrime(int n)
{
    if (n <= 1) return 0;
    if (n % 2 == 0) return n == 2;

    for (int i = 3; ; i += 2)
    {
        if (i > n/i) break;  // 等价于 i*i > n, 不用开方
        if (n % i == 0) return 0;
    }
    return 1;
}

int main()
{
    for (int n = 100; n <= 300; n++)
        if (IsPrime(n))
            printf("%4d", n);
    return 0;
}

Answer 2

{
if(n%i==0) 如果n被i除尽，那说明n不是素数
return(0);/*如果不是素数,返回0*/
}
比n小的所有i都不能除尽n，循环结束，那不就说明n满足素数的定义吗？
return 1;/*如果是素数,返回1*/

Answer 3

for(i=2;i<sqrt(n);i++)
最好改为
for(i=2;i<=sqrt(n);i++)

意思是：
假设n(存在)最大约数是i,那肯定有i*i<=n,
即i<=（√n)
sqrt()是c语言中求方根的函数
所以有i<=sqrt(n)

不知是不是这一块不懂。

Answer 4

应该是i<=sqrt(n)
如果一个数是合数，那么它的所有因子将不会超过它的开方

Answer 5

一个素数它只能被1和它自身整除，而不能被其他整数整除，这样判断一个数是素数我们关键就看它是否能被在1~它自身范围内的值其他值整除了。一个很正常的思路就是
for(i=2; i<n; i++)
{
if(n%i==0)
return 0;/*能够被整除，说明这个数不是素数，这个就会返回0*/
}
return 1;/*如果这个函数能运行到这一步，说明n%i==0没有成立过，就是n不能被2~n-1中任何一个数整除，所以就是素数*/
我们再来看看我们循环的范围是否一定需要2~n-1，不一定，我们可以优化一下程序，循环的范围只需要2~sqrt(n) (n平方根)就行了，想一想，判断一个数n能否整除大于sqrt(n)的数这是没必要的，因为这里肯定不能整除。还有这for循环中应该是i<=sqrt(n);