0

这个程序是一个 c++ 程序，它使用 Eratosthenes 的筛子来计算素数来找到素数。然后应该存储执行此操作所需的时间，并重新执行计算 100 次，每次存储时间。在这个程序中有两件事我需要帮助：

首先，我只能测试高达 4.8 亿的数字，我希望得到更高的数字。

其次，当我给程序计时时，它只会得到第一个计时，然后打印零作为时间。这是不正确的，我不知道时钟有什么问题。-谢谢您的帮助

这是我的代码。

#include <iostream>
#include <ctime>
using namespace std;

int main ()
{


    int long MAX_NUM = 1000000;
    int long MAX_NUM_ARRAY = MAX_NUM+1;
    int long sieve_prime = 2;
    int time_store = 0;
    while (time_store<=100)
    {
        int long sieve_prime_constant = 0;

        int *Num_Array = new int[MAX_NUM_ARRAY];
        std::fill_n(Num_Array, MAX_NUM_ARRAY, 3);
        Num_Array [0] = 1;
        Num_Array [1] = 1;


        clock_t time1,time2;
        time1 = clock();
        while (sieve_prime_constant <= MAX_NUM_ARRAY)
        {
            if (Num_Array [sieve_prime_constant] == 1)  
            {

                sieve_prime_constant++;
            }
            else
            {
                Num_Array [sieve_prime_constant] = 0;  
                sieve_prime=sieve_prime_constant; 
                while (sieve_prime<=MAX_NUM_ARRAY - sieve_prime_constant)  
                {
                    sieve_prime = sieve_prime + sieve_prime_constant;
                    Num_Array [sieve_prime] = 1;
                }
                if (sieve_prime_constant <= MAX_NUM_ARRAY)
                {
                    sieve_prime_constant++;
                    sieve_prime = sieve_prime_constant;
                }
            }
        }
        time2 = clock();
        delete[] Num_Array;
        cout << "It took " << (float(time2 - time1)/(CLOCKS_PER_SEC)) << " seconds to    execute    this loop." << endl;
        cout << "This loop has already been executed " << time_store << " times." << endl;
        float Time_Array[100];
        Time_Array[time_store] = (float(time2 - time1)/(CLOCKS_PER_SEC));
        time_store++;
    }


    return 0;

}
4

3 回答 3

0

这部分代码应该进入你的循环：

int *Num_Array = new int[MAX_NUM_ARRAY];
std::fill_n(Num_Array, MAX_NUM_ARRAY, 3);
Num_Array [0] = 1;
Num_Array [1] = 1;

编辑：这个也需要在循环中：

int long sieve_prime_constant = 0;

当我在我的机器上运行它时，每个循环需要 0.2 秒。如果我在 MAX_NUM_ARRAY 中添加两个零，则每次迭代需要 4.6 秒（直到第 20 个循环，我厌倦了等待超过 1.5 分钟）

于 2013-02-10T22:27:59.733 回答
0

I think the problem is that you don't reset the starting prime:

int long sieve_prime = 2;

Currently that is outside your loop. On second thoughts... That's not the problem. Has this code been edited to incorporate the suggestions in Mats Petersson's answer? I just corrected the bad indentation.

Anyway, for the other part of your question, I suggest you use char instead of int for Num_Array. There is no use using int to store a boolean. By using char you should be able to store about 4 times as many values in the same amount of memory (assuming your int is 32-bit, which it probably is).

That means you could handle numbers up to almost 2 billion. Since you are using signed long as your type instead of unsigned long, that is approaching the numeric limits for your calculation anyway.

If you want to use even less memory, you could use std::bitset, but be aware that performance could be significantly impaired.

By the way, you should declare your timing array at the top of main:

float Time_Array[100];

Putting it inside the loop just before it is used is a bit whack.

Oh, and just in case you're interested, here is my own implementation of the sieve which, personally, I find easier to read than yours....

std::vector<char> isPrime( N, 1 );

for( int i = 2; i < N; i++ )
{
    if( !isPrime[i] ) continue;
    for( int x = i*2; x < N; x+=i ) isPrime[x] = 0;
}
于 2013-02-10T23:07:20.487 回答
0

同意前面的评论。如果你真的想把事情搞定，你不会存储所有可能值的数组（如 int 或 char），而只保留素数。然后，您测试每个后续数字是否可通过迄今为止找到的所有素数进行整除。现在您只受到可以存储的素数数量的限制。当然，这不是您真正想要实现的算法......但由于它将使用整数除法，所以它非常快。像这样的东西：

int myPrimes[MAX_PRIME];
int pCount, ii, jj;
ii = 3;
myPrimes[0]=2;
for(pCount=1; pCount<MAX_PRIME; pCount++) {
    for(jj = 1; jj<pCount; jj++) {
        if (ii%myPrimes[jj]==0) {
            // not a prime
            ii+=2; // never test even numbers...
            jj = 1; // start loop again
        }
    }
    myPrimes[pCount]=ii;
}

不是你所要求的，但也许它是有用的。

于 2013-02-10T23:30:18.300 回答