打印质数从1到100

Question

此c++代码输出以下素数：3 5 7 11 13 17 19 23 31 31 37 41 47 53 59 61 67 71 73 79 83 89 97.

但我不认为我的书是这样写的。它提到了一个数字的平方根。因此，我确实尝试将我的第二个循环更改为for (int j=2; j<sqrt(i); j++)，但它并没有给出我所需要的结果。

我需要如何将这段代码修改成我的书所希望的那样呢？

int main () 
{
    for (int i=2; i<100; i++) 
        for (int j=2; j<i; j++)
        {
            if (i % j == 0) 
                break;
            else if (i == j+1)
                cout << i << " ";

        }   
    return 0;
}

素数是指有两个不同的除数的整数，即1和这个数本身。编写、运行和测试一个C++程序，该程序查找并打印所有小于100的素数。(提示:1是素数。对于从2到100的每个数字，查找RE余数=数字% n，其中n的范围从2到sqrt(数字)。如果n大于sqrt(数)，则这个数不能被n等除，为什么？如果任何余数等于0，则该数字不是素数。)

Answer 1

三种方式：

1.

int main () 
{
    for (int i=2; i<100; i++) 
        for (int j=2; j*j<=i; j++)
        {
            if (i % j == 0) 
                break;
            else if (j+1 > sqrt(i)) {
                cout << i << " ";

            }

        }   

    return 0;
}

2.

int main () 
{
    for (int i=2; i<100; i++) 
    {
        bool prime=true;
        for (int j=2; j*j<=i; j++)
        {
            if (i % j == 0) 
            {
                prime=false;
                break;    
            }
        }   
        if(prime) cout << i << " ";
    }
    return 0;
}

3.

#include <vector>
int main()
{
    std::vector<int> primes;
    primes.push_back(2);
    for(int i=3; i < 100; i++)
    {
        bool prime=true;
        for(int j=0;j<primes.size() && primes[j]*primes[j] <= i;j++)
        {
            if(i % primes[j] == 0)
            {
                prime=false;
                break;
            }
        }
        if(prime) 
        {
            primes.push_back(i);
            cout << i << " ";
        }
    }

    return 0;
}

编辑:在第三个例子中，我们跟踪所有以前计算过的素数。如果一个数可以被一个非素数整除，也有一些素数<=，它也是可除的除数。这减少了素数在范围/总范围的计算。

Answer 2

如果j等于sqrt(i)，那么它也可能是一个有效的因素，而不仅仅是当它更小的时候。

要在内部循环中迭代并包含sqrt(i)，可以编写：

for (int j=2; j*j<=i; j++)

(与使用sqrt(i)相比，这具有不需要转换为浮点数的优点。)

Answer 3

如果一个数字有除数，其中至少一个必须小于或等于该数字的平方根。当您检查除数时，您只需要检查到平方根，而不是一直到被测试的数目。