c++ - C编程-查找质数

一位 friend 给我此代码以查找1-40的质数

#include <stdio.h>
#include <conio.h>

void main(void)
{
    clrscr();

//print prime numbers from 1-40

int i, j;
int factor = 0; //this will be 1 if a factor is found
        //otherwise 0
        //so factor = 1 means not a prime number

printf("Prime numbers from 1 to 40 are: ");
for (i = 1; i < 41; i++)
{
    for (j = 2; j <= (i / 2); j++)
    {
        if (factor == 0)
        {
            if (i % j == 0)
                factor = 1;
            else
                factor = 0;
        }
    }
    if (factor != 1)
    {
        printf("%d ", i);
    }
    factor = 0;
}
getch();

}

我没有得到循环的第二部分。.为什么j以2开头，为什么它小于(i / 2)而不是i？

谢谢。

最佳答案

因为1是所有数字(包括质数)的因数，所以您无需为此进行测试。 (外循环可能也应该从2开始，因为按照惯例，通常不将1视为质数。)



无需检查大于i平方根的因数，因为如果存在这样的因数f，还将存在一个小于平方根的因果i/f。

但是平方根很难计算，因此此版本使用i/2作为更简单但更宽松的上限。只要i至少为4，它至少与平方根一样大。

关于c++ - C编程-查找质数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22061955/