Не находя времен первичного поколения / ограниченного поколения
Эта программа — программа на С ++, которая находит простые числа, используя сито эратосфена для вычисления простых чисел. Тогда предполагаемый сохранить время, необходимое для этого, и повторить расчет 100 раз, сохраняя время каждый раз. В этой программе мне нужно помочь с двумя вещами:
Во-первых, я могу тестировать только цифры до 480 миллионов, которые я бы хотел получить выше.
Во-вторых, когда я запускаю программу, она получает только первое время, а затем печатает нули как время. Это не правильно, и я не знаю, в чем проблема с часами. -Спасибо за помощь
Вот мой код
#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;
}
Решение
Этот раздел кода должен идти внутри вашего цикла:
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 минуты)
Другие решения
Я думаю, что проблема в том, что вы не сбрасываете начальное простое число:
int long sieve_prime = 2;
В настоящее время это за пределами вашей петли. Если подумать … Это не проблема. Был ли этот код отредактирован для включения предложений в ответ Матса Петерссона? Я только исправил плохой отступ.
Во всяком случае, для другой части вашего вопроса, я предлагаю вам использовать char вместо int за Num_Array, Нет смысла использовать int хранить логическое значение. Используя char вы должны иметь возможность хранить примерно в 4 раза больше значений в одном и том же объеме памяти (если int 32-битный, что, вероятно, и есть).
Это означает, что вы можете обрабатывать цифры почти до 2 миллиардов. Так как вы используете signed long как ваш тип вместо unsigned longто есть приближается к числовым пределам для вашего расчета.
Если вы хотите использовать еще меньше памяти, вы можете использовать std::bitset, но имейте в виду, что производительность может быть значительно ухудшена.
Кстати, вы должны объявить свой временной массив в верхней части main:
float Time_Array[100];
Поместить его в цикл непосредственно перед тем, как его использовать, — немного странно.
О, и на тот случай, если вам интересно, вот моя собственная реализация сита, которую лично мне легче читать, чем вашу ….
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;
}
Согласитесь с предыдущими комментариями. Если вы действительно хотите собрать что-то, вы не сохраняете массив всех возможных значений (как 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;
}
Не совсем то, что вы просили, но, возможно, это полезно.