Любые предложения относительно того, как я могу заставить эту программу работать на n = 1 триллион (помимо обновления/покупки нового компьютера)?
Ошибка следующая: после сборки программа выполняется (выскакивает окно вывода в стиле командной строки) и затем быстро закрывается, и я получаю следующую ошибку "ProjectPrimes.exe прекратил работу (Windows ищет решение для эта проблема." Я подозреваю, что это связано с проблемами памяти, поскольку я впервые столкнулся с этим при n = 20 миллионов, но это было до того, как я выбрал malloc/освобождение массива "решето" (т.е. мой массив "решето" - это большой массив размерами nx 1 и с каждым элементом, состоящим из 1 или 0).
Программа обрабатывает первые 300 миллионов целых чисел (16 252 325 простых чисел) примерно за 35 секунд, так что это нормально, но ничего особенного. Как я уже упоминал, цель состоит в том, чтобы иметь возможность генерировать простые числа ниже 1 триллиона, так что я далеко...
Если уместно, вот характеристики моей машины (на случай, если цель окажется необоснованной на этой машине): 2,40 ГГц i5, 4 ГБ ОЗУ, 64-битная Windows 7.
Обзор методологии, для тех, кто не знаком: мы используем подход решета Сундарама. Не вдаваясь в доказательство, мы сначала удалим все нечетные непростые числа ниже целого числа «n», используя функцию решета: [2*(i+j+2*i*j)+1 | i ‹- [1..n/2], j ‹- [i..оптимизированная верхняя граница]]. Затем мы вычеркиваем четные числа (кроме двух, конечно). Что оставляет нас с простыми числами.
Почему функция простого числа возвращает (указатель на массив, содержащий) полный набор простых чисел меньше n? Что ж, цель состоит в том, чтобы иметь возможность идентифицировать как (i) количество простых чисел меньше n, так и (ii) перечислить простые числа меньше n. Именно поэтому я решил передать в качестве аргумента указатель на количество простых чисел меньше n.
Вот не очень интересная «основная» функция:
int main() {
long ceiling = 300*1000*1000;
long *numPrimes;
long *primes;
primes = primesToSS(ceiling+1, numPrimes);
printf("\n\nThere are %d primes below %d.\n\n",*numPrimes,ceiling);
free(primes);
return 0;
}
А вот и мясо:
//n represents the ceiling, i.e., the integer below which we will generate primes
//cnt* is a pointer which will point the number of primes below n
long* primesToSS( long n, long* cnt ) {
//initialize sieve by setting all elements equal to 1 (except for 0 and 1)
long *sieve = malloc(n*sizeof(long));
initArray(sieve, n, 1);
sieve[0] = 0; sieve[1] = 0;
//eliminate all odd composite numbers
for (int i = 1; i <= n/2; ++i)
for (int j = i; j <= (n-2*i)/(2*(2*i+1)); ++j)
sieve[ 2*(i+j+2*i*j)+1 ] = 0;
//eliminate all even numbers greater than two
//and count total number of primes below n
long numPrimes = 1;
for (int i = 3; i < n; ++i) {
if (i % 2 == 0) sieve[i] = 0;
numPrimes += sieve[i];
}
*cnt = numPrimes;
//create array of primes
long *primes = malloc(numPrimes*sizeof(int));
long counter = 0;
for (int i = 0; i < n; ++i) {
if (sieve[i] == 1) {
primes[counter] = i;
counter++; }
}
free(sieve);
return primes;
}
void initArray( int* arr, int len, int n ) {
for( int i = 0; i < len; ++i) arr[i] = n; }
numPrimesне инициализируется, когда вы передаете егоprimesToSS(). Внутри этой функции строка*cnt = numPrimes;будет записываться в случайное место в памяти. - person Blastfurnace schedule 06.10.2014%ldв своих форматах для печатиlongзначений. Также кажется немного чрезмерным использование 64-битных значенийlongдля хранения значений 0 или 1. Если вы используете отдельные биты, вы сможете хранить гораздо больше значений в сите. Вы также можете подумать о том, чтобы вообще не беспокоиться о хранении четных чисел; массив битов может просто кодировать нечетные числа (но это позволяет вам получить 128 чисел в каждый элемент массива, где в настоящее время вы получаете только 1). - person Jonathan Leffler schedule 06.10.2014intи изменил его наlongв попытке обработать более крупные простые числа, но не выполнил полную или тщательную работу. - person Jim Balter schedule 06.10.2014numPrimesявляется одновременно указателем указывающим ни на что (в main()) и длинным целым числом (в другом месте) - person joop schedule 06.10.2014