c++ - 这个计算素数的程序能走多远？

Question

#include <iostream>

using namespace std;

int ifprime(long long int);
int main()

{
    long long int number;   
    cout<<"Enter the number of prime numbers you want to know:\n";
    cin>>number;    //number is the number of prime numbers to be displayed
    long long int j=0;
    long long int m=2;      //m would be used as consecutive natural numbers on which, test of prime number is performed

    while (1<2)
    {
        if(ifprime(m)==1)
        {
            j+=1;   // j is the counter of the prime numbers found and displayed
            cout<<m<<endl;
        }
        m+=1;
        if(j==number)
        {
            break;
        }
    }

}

int ifprime(long long int a)
{
    for(int i=2;i<a;i++)
    {
        if(a%i==0)
        {
            return 0;
        }
    }
    return 1;
}

与已知的最大素数相比，long long int 的范围似乎很小:/

即使我要计算 long long int 范围内的最后一个素数，我是否可以计算计算该数字所需的时间？

Answer 1

假设最大的质数是 n = 13。然后您的程序将尝试以下数字:2, 3, 4,.. 11, 12所以你必须测试你的数字 n - 2 次(或多或少 n 次)并且直到你到达那一点你的程序必须经过 2, 3, 4, ... 11, 12, 13，这也是(或多或少)n 次。 -->复杂度为O(n^2)。加快程序速度的简单提示:将您目前找到的每个质数存储在 std::vector 中，并且只尝试这些。这样您就可以避免整数分解(例如除以 6 (2 * 3) 或 8 (2 * 2 * 2))。