找到Primes的有效方式 [英] Efficient way of finding Primes

问题描述

我有一个循环，从3到phi的两个主要用户输入的数字（这些数字可以是任何长度），找到所有的素数之间的两个，并将它们存储在一个数组。

I have a loop that goes from 3 to the phi of two prime user-inputted numbers (these numbers can be any length), finds all the prime numbers between the two, and stores them into an array.

我的循环代码：

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

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

This loop takes a long period of time to finish.

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.

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

I need this loop to work at a faster speed. Is there a more efficient method of performing this action?

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

P.S. My loop calls another function,isPrime, here is the code for it if anyone wanted it.

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

推荐答案

是，您想要查找某些范围内的所有素数 [a，b] 。

They way I read your question is, that you want to find all primes in some range [a,b].

内存，最快的方法是使用筛选Eratosthenes 。 Wikipedia有一个很好的演示如何工作：

If you have enough memory, the fastest way to do this, is probably using the Sieve of Eratosthenes. Wikipedia has a good demo of how it works:

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

列表中的第一个数字是2;在
列表中的每个第二个数字交叉，然后从2以2递增计数（这将使
是列表中的2的倍数）：

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

2后的列表中的下一个数字是3;交叉出每个
列表后面的第三个数字，从3开始，以
3（这将是列表中的3的倍数）递增计数：

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

3后的列表中未删除的下一个数字为5;在5之后以5为增量从5开始递增计数，从列表中的第5个数字开始递减计数（即所有5的倍数）：

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

b $ b

这比检查每个数字是否为素数更快，因为外循环只运行每个素数，内循环运行得更快更快。素数的倒数之和为 loglogn ，所以总共你会得到 O（nloglogn）的时间。比你目前的 O（n ^ 2）或 O（n ^（3/2））优先检查。

This is faster than checking if each number is a prime, since the outer loop only runs over every prime, and the inner loop runs faster and faster. The sum of reciprocals of primes is loglogn, so in total you get O(nloglogn) time. Much better than your current O(n^2) or O(n^(3/2)) with faster prime checking.

这篇关于找到Primes的有效方式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！