c++ - 寻找质数的有效方法

Question

我有一个循环，从 3 到用户输入的两个质数的 phi(这些数可以是任意长度)，找到两者之间的所有质数，并将它们存储到一个数组中。

我的循环代码:

int coPrimes(int num)
{
    for (int i=3; i<=num; i++)
        if(isPrime(i))
            coprimes.push_back(i);

这个循环需要很长时间才能完成。

Enter a prime number for 'a': 601
Enter a prime number for 'b': 769
a value: 601
b value: 769
product: 462169
phi: 460800
pubKey: 19
privKey: 145515

Process returned 0 (0x0)   execution time : **756.670 s**
Press any key to continue.

我需要这个循环以更快的速度工作。是否有更有效的方法来执行此操作？

附言我的循环调用另一个函数，isPrime，如果有人需要的话，这里是它的代码。

bool isPrime(int num)
{
    bool prime = true;

    if(num < 2)
        prime = true;
    for (int i=2; i<num; i++)
        if (num % i == 0)
            prime = false;
    return prime ;
}

Answer 1

我读到你的问题的方式是，你想找到某个范围内的所有素数 [a,b]。

如果你有足够的内存，最快的方法可能是使用 Sieve of Eratosthenes .维基百科有一个关于它如何工作的很好的演示:

2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

First number in the list is 2; cross out every 2nd number in the list after it by counting up from 2 in increments of 2 (these will be all the multiples of 2 in the list):

2  3  x  5  x  7  x  9   x 11  x 13  x 15  x 17  x 19  x 21  x 23  x 25

Next number in the list after 2 is 3; cross out every 3rd number in the list after it by counting up from 3 in increments of 3 (these will be all the multiples of 3 in the list):

2  3  x  5  x  7  x  x   x 11  x 13  x  x  x 17  x 19  x  x  x 23  x 25

Next number not yet crossed out in the list after 3 is 5; cross out every 5th number in the list after it by counting up from 5 in increments of 5 (i.e. all the multiples of 5):

2  3  x  5  x  7  x  x   x 11  x 13  x  x  x 17  x 19  x  x  x 23  x  x

这比检查每个数字是否为素数更快，因为外循环只遍历每个素数，而内循环运行得越来越快。素数的倒数之和为 loglogn，因此总共有 O(nloglogn) 时间。比您当前的 O(n^2) 或 O(n^(3/2)) 更快的质数检查要好得多。