优化质数编码？

Question

我写这段代码是为了显示1到100之间的素数。唯一的条件是不要使用函数，整个代码应该是内联的。我会问我是否可以改进(优化)它更多？

#include<iostream>

using namespace std;

int main() {

    int i=2,j=2;

    cout<<"Prime numbers between 1 and 100 are:"<<endl;
    cout<<"2"<<"\t";
    while(i!=100) {
        for(int j=2;j<i;j++) {
            if(i%j==0)
            break;

            if(j==i-1)
            cout<<i<<"\t";
        }

        i++;
    }

    cout<<endl;
    system("pause");
    return 0;
}

Answer 1

您正在检查从2到100的每个数字。但由于2是唯一的偶质数，你可以跳过2之后的每个偶数，这对i和j都适用。因此，从3开始i和j，并将它们递增2。

#include<iostream>

using namespace std;

int main() {
    cout<<"Prime numbers between 1 and 100 are:"<<endl;
    cout<<"2"<<"\t";
    for (int i=3; i<100;i+=2) {
        // This loop stops either when j*j>i or when i is divisible by j.
        // The first condition means prime, the second, not prime.
        int j=3;
        for(;j*j<=i && i%j!=0; j+=2); // No loop body

        if (j*j>i) cout << i << "\t";
    }
    cout<<endl;
    return 0;
}

除了上面提到的技巧之外，我还添加了逻辑上与j<=sqrt(i)完全相同的条件j*j<=i。当你可以做一个简单的乘法时，不需要计算平方根。

Answer 2

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

这个不是很好。

首先，您只需要检查j <= sqrt(i)，因为例如7永远不会在没有休息的情况下除以12。

其次，您应该跟踪所有以前找到的素数；将其保存在向量中，并且仅针对其内容和我编写的条件执行此循环。

Answer 3

你可以优化你现有的代码：

在while循环中，您的步长应该是2，这样您就不会测试偶数。

• 在

循环中，您应该在到达要测试的数字的平方根时停止

您可以使用不同的方法：

Erastoses的

• 筛子：http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

在Erastoses的筛子上，只需删除可被2、3和5除以的数字，就可以显着减少您需要测试素性的次数。