优化素数代码? [英] Optimizing prime numbers code?

问题描述

我编写了这段代码来显示1到100之间的质数.唯一的条件是不使用函数，整个代码应该是内联的.我会问我是否可以进一步改善(优化)?

I wrote this code to show the primes between 1 and 100. The only condition is to do not use functions, whole code should be inline. I would ask if I can improve (optimize) it much more?

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

推荐答案

您正在检查2到100之间的每个数字.但是由于2是唯一的偶数质数，因此可以跳过2之后的每个偶数. i 和 j .因此，将 i 和 j 从3开始，并将它们增加2.

You are checking every number from 2 to 100. But since 2 is the only even prime number, you can skip every even number after 2. This goes for both i and j. So start i and j at 3, and increment them by 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 * j< = i ，从逻辑上讲，该条件与 j< = sqrt(i)完全相同>.可以进行简单的乘法运算时，无需计算平方根.

In addition to the trick mentioned above, I've added the condition j*j<=i which logically is the exact same as j<=sqrt(i). There's no need to compute the square root when you can do a simple multiplication.

这篇关于优化素数代码?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！