c++ - 打印从 1 到 100 的素数

Question

此 c++ 代码打印出以下素数:3 5 7 11 13 17 19 23 29 31 37 41 43 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;
}

A prime integer number is one that has exactly two different divisors, namely 1 and the number itself. Write, run, and test a C++ program that finds and prints all the prime numbers less than 100. (Hint: 1 is a prime number. For each number from 2 to 100, find Remainder = Number % n, where n ranges from 2 to sqrt(number). \ If n is greater than sqrt(number), the number is not equally divisible by n. Why? If any Remainder equals 0, the number is no a prime number.)

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;
}

编辑:在第三个示例中，我们跟踪所有之前计算的素数。如果一个数可以被一个非素数整除，那么还有一些素数 <= 这个除数也可以被它整除。这将计算量减少了 primes_in_range/total_range。