SO上也有这样的问题，但争议一直拖在那里。有没有一种快速方法可以找到给定素数之后的下一个素数来扩展哈希表？
示例（根据@MBo的推荐更新代码）
size_t get_next_prime_number(size_t current_prime_number)
{
size_t saved = current_prime_number;
bool is_prime = true;
if (current_prime_number >= MIN_PRIME_NUMBER)
for(current_prime_number = current_prime_number + 2; current_prime_number < SIZE_MAX; current_prime_number += 2)
{
// previous: for(size_t j = 2; j < current_prime_number; ++j)
for(size_t j = 3; j*j <= current_prime_number; j +=2)
if (current_prime_number % j == 0)
{
is_prime = false;
break;
}
else
is_prime = true;
if (is_prime)
break;
}
return (current_prime_number == saved) ? 0 : current_prime_number;
}
更新
我尝试使用分成简单的建议，但没有成功Floating point exception。
#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MIN_PRIME_NUMBER 2 // > 1
#define DIVIDER_LIMIT 65535 // sqrt(4294967295)
#define INDEX_DIFFERENCE 10 // > 1
void resize_array_up(size_t * stored_primes, const size_t prime_position)
{
if (prime_position % INDEX_DIFFERENCE == INDEX_DIFFERENCE - 1)
if (!realloc(stored_primes, (prime_position + INDEX_DIFFERENCE + 1) * sizeof(size_t)))
exit(EXIT_FAILURE);
stored_primes = memset(stored_primes, 0, sizeof(size_t));
}
size_t get_next_prime_number(const size_t current_prime_number, const size_t prime_position, size_t * stored_primes)
{
resize_array_up(stored_primes, prime_position);
size_t saved_current = current_prime_number,
prime_number = 1;
if ((current_prime_number >= MIN_PRIME_NUMBER) && (prime_position < SIZE_MAX) && (current_prime_number < SIZE_MAX))
{
for(size_t divider = sqrt(current_prime_number), number = divider * divider, temporary_number = current_prime_number + 2;
(divider < DIVIDER_LIMIT) && (number <= temporary_number); divider += 2, number = divider * divider, temporary_number += 2)
for(size_t counter = 0; counter <= prime_position; ++counter)
{
if ((number % stored_primes[counter]) == 0)
break;
else
prime_number = number;
}
}
return (prime_number == saved_current) ? 0 : prime_number;
}
int main(void)
{
size_t * primes = calloc(INDEX_DIFFERENCE, sizeof(size_t));
if (primes)
{
size_t prime_position = 0,
prime_number = MIN_PRIME_NUMBER;
primes[prime_position] = prime_number;
do
{
prime_number = get_next_prime_number(prime_number, prime_position++, primes);
printf("%zu\n\n", prime_number);
}
while (prime_number != 0);
if (prime_number == 0)
free(primes);
}
else
exit(EXIT_FAILURE);
return EXIT_SUCCESS;
}
