c++ - C语言编程——寻找素数

Question

一个 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？

谢谢。

Answer 1

why does j start with 2

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

and why is it less than (i / 2) and not i?

没有必要检查大于 i 平方根的因数，因为如果有这样的因数 f，也会有一个因数 i/f 小于平方根。

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