Что вы всегда должны делать, это писать свою программу по частям и проверять, работает ли она после завершения каждой функции, прежде чем переходить к новой. Так как вы затем тестируете каждую функцию, которую реализуете отдельно, вы знаете, что любые ошибки наиболее вероятны в функции, которую вы реализовали последней.
В вашем случае эта проблема сразу бросается в глаза:
for (int multiples = 2; prime[j * multiples] <= number; multiples++){
prime[j * multiples] = false;
}
Здесь вы тестируете prime[j * multiples] <= number, то есть сравниваете флаг с числом. Поскольку поздние флаги обнуляются до конца массива, j*multiples выйдет за пределы массива prime[] и в конечном итоге приведет к аварийному завершению вашей программы.
Тест должен быть, конечно, j * multiples <= number.
Поскольку я работаю по одной функции и одной проблеме за раз, я не знаю, является ли это единственной проблемой, с которой сталкивается твой код. Выяснить это ваша задача. На вашем месте я написал бы кусочно, возможно, при тестировании количество printf() s, чтобы убедиться, что каждая часть работает, чтобы я мог положиться на код, который я уже написал, сосредоточиться на этой части и сделать устойчивый прогресс с минимальным разочарованием.
В последнее время было довольно много вопросов относительно сит Эратосфена. Я всегда считал полезным реализовать абстрактный, динамически размещаемый тип сита и простые функции доступа / модификатора для его изменения. Поскольку в программе должно быть только одно сито, его можно описать с помощью глобальных переменных:
#include <stdlib.h>
#include <inttypes.h>
#include <limits.h>
#include <string.h>
#include <stdio.h>
/* This is the number of bits in an unsigned long.
The exact value is floor(log(ULONG_MAX + 1)/log(2)),
but the following definition will be correct on all
modern architectures: */
#define ULONG_BITS (sizeof (unsigned long) * CHAR_BIT)
/* Prime sieve, with a flag for zero and each odd integer,
one bit per flag. */
static unsigned long *sieve = NULL;
/* Largest positive integer within the sieve. */
static uint64_t sieve_max = 4;
/* Number of unsigned longs allocated and initialized in the sieve. */
static size_t sieve_words = 0;
/* Function to discard the sieve, if no longer needed. */
static inline void sieve_free(void)
{
free(sieve); /* free(NULL); is safe, and does nothing. */
sieve = NULL;
sieve_max = 4; /* Since 0, 1, 2, 3, 4 give built-in answers */
sieve_words = 0;
}
Исходное значение sieve_max равно 4, потому что наша тестовая функция is_prime() обрабатывает 0, 1, 2 и 3 простых числа и все большие четные целые числа в любом случае не простые; это означает, что целые числа от 0 до 4 всегда известны нашим is_prime():
/* Return 1 if number is prime according to sieve,
0 if known composite/not prime. */
static inline int is_prime(const uint64_t number)
{
/* 0, 1, 2, and 3 are considered prime. */
if (number <= 3)
return 1; /* Prime */
/* All larger even integers are not prime. */
if (!(number & 1))
return 0; /* Not prime */
/* Outside the sieve? */
if (number > sieve_max) {
fprintf(stderr, "is_prime(): %" PRIu64 " is outside the sieve!\n", number);
exit(EXIT_FAILURE);
}
{
const uint64_t half = number / 2;
const size_t w = half / ULONG_BITS;
const unsigned long m = 1uL << (half % ULONG_BITS);
/* The flag for odd number is (number/2)th.
half / ULONG_BIT is the word where bit
half % ULONG_BIT is in.
Return 0 if the bit is set, 1 if clear. */
return !(sieve[w] & m);
}
}
Мы можем очень легко вырастить сито, установив по умолчанию все новые флаги как "не простые":
static void sieve_upto(const uint64_t max)
{
/* Number of words needed for (max+1)/2 bits. */
const uint64_t nwords = 1 + max / (2 * ULONG_BITS);
const uint64_t nbytes = nwords * (uint64_t)sizeof (unsigned long);
const size_t words = (size_t)nwords;
const size_t bytes = words * sizeof (unsigned long);
unsigned long *temp;
/* Already covered by the current sieve? */
if (sieve_max > max)
return;
/* We need to be able to handle max+1,
and neither bytes or words should overflow. */
if (max >= UINT64_MAX ||
(uint64_t)words != nwords || (uint64_t)bytes != nbytes) {
fprintf(stderr, "sieve_upto(): %" PRIu64 " is too high a maximum.\n", max);
exit(EXIT_FAILURE);
}
/* Do we already have all the bytes we need? */
if (words == sieve_words) {
sieve_max = max;
return;
}
/* Allocate/reallocate. Note that realloc(NULL, size)
is equivalent to malloc(size), so this is safe
even if 'sieve' is NULL. */
temp = realloc(sieve, bytes);
if (!temp) {
fprintf(stderr, "Not enough memory for a sieve up to %" PRIu64 ".\n", max);
exit(EXIT_FAILURE);
}
sieve = temp;
/* Clear the new words to all zeros. */
memset(sieve + sieve_words, 0, (words - sieve_words) * sizeof (unsigned long));
sieve_max = max;
sieve_words = words;
}
Наконец, нам нужна функция, которая будет отмечать составное число (не простое):
static inline void not_prime(const uint64_t number)
{
/* Primality is internally handled for 0, 1, 2, 3, and 4. */
if (number <= 4)
return;
/* All larger even numbers are internally handled. */
if (!(number & 1))
return;
/* Outside the sieve? */
if (number > sieve_max) {
fprintf(stderr, "not_prime(): %" PRIu64 " is outside the sieve!\n", number);
exit(EXIT_FAILURE);
}
{
const uint64_t half = number / 2;
const size_t w = half / ULONG_BITS;
const unsigned long m = 1uL << (half % ULONG_BITS);
/* Half is the bit index in sieve[].
half / ULONG_BITS is the word containing the bit
half % ULONG_BITS that needs to be set. */
sieve[w] |= m;
}
}
Сито строительства Эратосфена Я оставлю вам; Моя цель - показать, как можно создать и управлять относительно эффективным (то есть сбалансированным использованием памяти и временем выполнения) для нечетных натуральных чисел, используя динамическое управление памятью.
( Проверка того, что простое сито Эратосфена находит все 455 052 511 простых чисел менее 10 000 000 000, занимает менее 90 секунд, и что для всех 323-разрядных простых чисел 203 280 221 требуется менее 30 секунд на моем ноутбуке, используя одно ядро и вышеупомянутые функции. Для более высоких диапазонов лучше использовать оконное сито. Обратите внимание, что функции подсчета простых чисел не учитывают 0 и 1 простые, в отличие от приведенных выше is_prime().)