打印从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;
}

素数是具有两个不同除数的整数,即1和数字本身.编写,运行和测试C++程序,查找并打印小于100的所有素数.(提示:1是素数.对于每个从2到100的数字,找到Remainder = Number%n,其中n的范围是2 to sqrt(number).\如果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;
}

编辑:在第三个例子中,我们跟踪所有先前计算的素数.如果一个数字可以被一个非素数除尽,那么还有一些素数<=该除数它也可以被除数.这减少了计算的primes_in_range/total_range因子.

Answer 2

如果j是等于给sqrt(i)它也可能是一个有效的因素,而不是只有当它的小.

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

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

(与使用sqrt(i)它相比,有一个优点是不需要转换为浮点数.)

Answer 3

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

Answer 4

这是我非常简单的c ++程序,用于列出2到100之间的素数.

for(int j=2;j<=100;++j)
{
    int i=2;
    for(;i<=j-1;i++)
    {
        if(j%i == 0)
            break;
    }

    if(i==j && i != 2)
        cout<<j<<endl;
}

Answer 5

使用Sieve of Eratosthenes逻辑，我能够以更快的速度获得相同的结果。

我的代码演示VS接受了答案。

与 相比count，我的代码完成工作所需的迭代要少得多。最后检查不同N值的结果。

为什么此代码比已经接受的代码性能更好：

- 在整个过程中偶数不会被检查一次。

- 内循环和外循环都只在可能的范围内进行检查。没有额外的检查。

代码：

int N = 1000; //Print primes number from 1 to N
vector<bool> primes(N, true);
for(int i = 3; i*i < N; i += 2){    //Jump of 2
    for(int j = 3; j*i < N; j+=2){  //Again, jump of 2
        primes[j*i] = false;
    }
}
if(N >= 2) cout << "2 ";
for(int i = 3; i < N; i+=2){        //Again, jump of 2
    if(primes[i] == true) cout << i << " "; 
}

对于N = 1000，我的代码需要 1166 次迭代，接受的答案需要 5287（慢 4.5 倍）

对于N = 10000，我的代码需要 14637 次迭代，接受的答案需要 117526（慢 8 倍）

对于N = 100000，我的代码需要 175491 次迭代，接受的答案需要 2745693（慢 15.6 倍）