1

我正在尝试自己实现筛子，除了提供的算法之外没有任何帮助......

#include <iostream>

using namespace std;

void findPrimeNumbers(int number) {

    int n=0;

    bool* boolArray = new bool[number](); 

    for(int i=0; i<number; i++) {
        boolArray[i] = true;
    }

    for(int i = 2; i<(int)sqrt(number); i++) {
        cout << "calculating...\n";
        if(boolArray[i]) {
            for(int j=(i^2+(n*i)); j<number; n++)
                boolArray[j] = false; 
        }
        if(boolArray[i])
            cout << i << "\n";
    }
    return;
}

int main()
{

    findPrimeNumbers(55);

    system("pause");
    return 0;
}

除了程序挂在第 37 行；具体来说，“boolArray[j] = false”。它永远不会退出那个循环，我不知道为什么。

编辑：好的，这解决了问题但仍然不正确，但不要回答，我想弄清楚:)

#include <iostream>
#include <cmath>

using namespace std;

void findPrimeNumbers(int number) {

    int n=0;

    bool* boolArray = new bool[number](); 

    for(int i=0; i<number; i++) {
        boolArray[i] = true;
    }

    for(int i = 2; i<sqrt(number); i++) {
        if(boolArray[i]) {
            for (int j = pow(i,2) + n*i; j <= number; j = pow(i, 2) + (++n*i))
                boolArray[j] = false;
        }
        if(boolArray[i] && number % i == 0)
            cout << i << "\n";
    }
    return;
}

int main()
{

    findPrimeNumbers(13195);

    system("pause");
    return 0;
}
4

4 回答 4

0

您的问题是i^2+(n*i)评论指出的那一行，operator^是 XOR 运算符，而不是求幂。为了对某些东西求幂，您必须包含<cmath>标题并std::pow(a,b)在它与数学表达式等效的地方调用a^b。

尽管您没有要求进行代码审查，但应该注意，对 bool 数组使用动态分配可能不是一个好主意。你应该使用std::vector<bool>并正确reserve调用。还应该注意的是，pow调用是完全没有必要的，因为您只是将它自身相乘（即 2^2 与 2*2 相同）。

更好的朴素初筛将类似于以下内容：

#include <vector>
#include <iostream>

template<typename T>
std::vector<T> generatePrimes(unsigned int limit) {
    std::vector<T> primes;
    std::vector<bool> sieve((limit+1)/2);
    if(limit > 1) {
        primes.push_back(2);
        for(unsigned int i = 1, prime = 3; i < sieve.size(); ++i, prime += 2) {
            if(!sieve[i]) {
                primes.push_back(prime);
                for(unsigned int j = (prime*prime)/2; j < sieve.size(); j += prime)
                    sieve[j] = true;
            }
        }
    }
    return primes;
}

int main() {
    std::vector<unsigned> primes = generatePrimes<unsigned>(1000000);
    for(auto& i : primes)
        std::cout << i << '\n';
}

你可以在这里看到它。

于 2013-01-26T03:41:31.620 回答
0

除了@Rapptz 指出的错误（^ 是按位异或）之外，您正在递增 n 而不是 j，因此永远不会达到终止条件。

于 2013-01-26T03:42:03.833 回答
0

你有很多问题：

int j=(i^2+(n*i))

^不是 C++ 中的权力，它是按位 XOR 运算符。要解决此问题，您需要使用#include <cmath>并使用pow，或简单地使用i * i.

其次，正如其他人所提到的，您正在增加n. 最简单的解决方法是改用while循环：

int j = std::pow(i, 2) + (n*i);
while(j < number) {
    //Set bool at index to false
    j += i;
}

第三，你有内存泄漏——你new没有delete. 此外，没有理由在new这里使用，而是您应该：

bool b[number];

这将在函数退出时自动释放 b。

最后，为什么return在void函数的底部？从技术上讲，您可以做到，但没有理由这样做。

于 2013-01-26T03:43:14.433 回答
0

两个问题：

^运算符不像其他一些语言那样是指数运算符。只需乘以i自身而不是 ( i*i)。

你的for循环：

for(int j=(i^2+(n*i)); j<number; n++)
    boolArray[j] = false;

不会重新评估每个循环的初始条件。您需要在for循环开始时重新评估条件：

for(int n=0; j<number; n++)
{
    j=(i*i+(n*i));
    boolArray[j] = false; 
}
于 2013-01-26T03:46:05.750 回答