主页 / 问题 / 1604109
Accepted
Чёрный Монах
Asked:2025-01-05 18:36:49 +0000 UTC2025-01-05 18:36:49 +0000 UTC

列出从 1 开始的素数的最快算法？

  • 772

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;
}
алгоритм

3 个回答

  1. Best Answer

    哦，我明白了，我们这里说的是埃拉托斯特尼筛法。操作的原则是删去不需要的。 在此输入图像描述

    #include <stdio.h>
#include <stdlib.h>

void sitoera(int n) {
    // Создаем массив для хранения информации о простоте чисел
    // здесь индекс массива будет числом, значнеие массива будет говорить оно простое True или нет False
    // размеры тут самому определить

    int* stored_primes = (int*)malloc((n + 1) * sizeof(int));
    for (int i = 0; i <= n; i++) {
        stored_primes[i] = 1; // Изначально все элементы True
    }
    stored_primes[0] = stored_primes[1] = 0; // 0 и 1 не являются простыми числами False

    for (int p = 2; p * p <= n; p++) { //пробегаем весь массив
        if (stored_primes[p]) {              // если значение массива True
            for (int i = p * p; i <= n; i += p) {  // пробегаем по индексам кратным p 
                stored_primes[i] = 0; // Отмечаем кратные p как непростые False
            }
        }
    }
    //Когда весь массив заполнен
    // Выводим все простые числа которые True
    printf("Простые числа до %d:\n", n);
    for (int i = 2; i <= n; i++) {
        if (stored_primes[i]) {
            printf("%d ", i);
        }
    }
    printf("\n");

    // Освобождаем память
    free(stored_primes);
}

int main() {
    int n = 10000; // Задайте верхний предел для поиска простых чисел
          sitoera(n);
    return 0;
}

    2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 1009 1013 1019 1021 1031 1033 1039
    • 3

  2. 更新正如评论中正确指出的那样，这不是埃拉托色尼的筛子。具有预览和划掉大数合数功能的真实筛选器的工作速度要快很多倍，并且占用的内存更少。

    这是使用埃拉托斯特尼筛法对素数进行顺序枚举的准备。当在搜索过程中找到下一个素数时，它将被添加到筛子中。

    #include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#include <math.h>

typedef uint32_t prime_t;

struct Sieve
{
    size_t count;
    prime_t *primes;
};

prime_t small_primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
                          47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};

void init_Sieve(struct Sieve *sieve)
{
    sieve->count = sizeof(small_primes) / sizeof(small_primes[0]);
    sieve->primes = (prime_t *)malloc(sieve->count * sizeof(small_primes[0]));

    memcpy(sieve->primes, small_primes, sieve->count * sizeof(prime_t));
}

void dispose_Sieve(struct Sieve *sieve)
{
    free(sieve->primes);
}

void append_Sieve(struct Sieve *sieve, prime_t prime)
{
    sieve->count++;
    sieve->primes = realloc(sieve->primes, sieve->count * sizeof(prime_t));
    sieve->primes[sieve->count - 1] = prime;
}

prime_t last_Sieve(struct Sieve *sieve)
{
    return sieve->primes[sieve->count - 1];
}

uint32_t int_sqrt(uint64_t n)
{
    return (uint32_t)floor(sqrt(n));
}

bool is_prime_Sieve(struct Sieve *sieve, uint64_t n)
{
    int32_t limit = int_sqrt(n);
    for (size_t i = 0; i < sieve->count; i++)
    {
        uint32_t p = sieve->primes[i];
        if (p > limit)
        {
            return true;
        }
        if (n % sieve->primes[i] == 0)
        {
            return false;
        }
    }
}

prime_t next_prime_Sieve(struct Sieve *sieve)
{
    uint64_t candidate = last_Sieve(sieve) + 2;
    while (true)
    {
        if (is_prime_Sieve(sieve, candidate))
        {
            return candidate;
        }
        candidate += 2;
    }
}

#include <stdio.h>
#include <unistd.h>

int main(int argc, char const *argv[])
{
    int num = 100;
    struct Sieve sieve;
    init_Sieve(&sieve);
    for (size_t i = 0; i < num; i++)
    {
        printf("%d\n", sieve.primes[i]);
    }

    num -= sieve.count;

    for (int i = 0; i < num; i++)
    {
        prime_t prime = next_prime_Sieve(&sieve);
        printf("new prime: %d\n", prime);
        append_Sieve(&sieve, prime);
    }
    dispose_Sieve(&sieve);
    return 0;
}

    更新

    下面是关于加速。事实证明，建议的食谱并没有多大帮助。

    我在旧的 Xeon 处理器上做了一个小基准测试：搜索前一百万素数

    sieve_1_1: 4.510699915 s
sieve_100_1: 4.502938856 s
sieve_100_1.4: 4.501762310 s
sieve2: 4.498788561 s
Sieve.cpp: 4.495656952 s
Sieve2.cpp: 4.495942813 s
    • sieve_1_1 未经优化的强力搜索。
    • sieve_100_1 每次重新分配都会增加 10000 个数字的容量。
    • sieve_100_1.4：每次迭代时，realloc 步骤增加 1.4 倍。
    • sieve2 绘制素数平方数组，以便在迭代除数时不取平方根。
    • Sieve.cpp 和 Sieve2.cpp 的功能与 sieve_1_1 和 sieve2 相同，但用于存储std::vector

    正如您所看到的，所有算法的工作原理大致相同。

    旧文本

    我怎样才能加快速度？首先，添加一个新的简单是相当昂贵的，每次都会进行重新分配。您可以在下一次重新分配时添加cap和 ，以常数或乘数增加上限。

    其次，搜索素数时，不能搜索所有奇数，而是跳过那些能被2、3、5整除的数字。这样搜索速度大约会提高一倍。如果你感兴趣，我会寻找它 - 在我的缓存中的某个地方，我有关于如何根据我们不想除以的数字进行移位的标志。它们可以简单地使用中国剩余定理来编译。

    第三，您可以将素数平方表与素数表一起拖动，而不是提取平方根。这将消除在寻找除数时计算平方根的需要。

    • 1

  3. 算法速度要求

    一旦找到下一个素数并且问题解决了，下一步就是重新分配哈希表中的桶。这将花费O(p)时间，其中p是找到的素数。也就是说，任何比线性时间更快找到数字的算法都适合我们。因为它的操作时间与重建表所花费的时间相比是微不足道的。这是从O大的角度进行的估计，对于小尺寸，该常数仍然很重要。

    检查直到√n 的所有因子大约需要√n · log n时间，其中第一个因子是检查一个数字，第二个因子是在找到素数之前需要检查的数字的平均数量。我要补充的是，这个估计被大大高估了，因为合数的检查总是在到达√n之前结束。而且这种检查通常会更早结束。

    注意：以下观察与此相关：如果从搜索中排除所有偶数素数候选者，则下一个素数的搜索速度不会加倍。因为我们丢弃了那些能被二整除的数字，它们几乎立即离开了枚举除数的循环。这并不意味着不需要这种优化，而是意味着您不应该对其期望过高。速度不会快一倍。

    我同意我们应该努力编写快速搜索，但不要狂热。过度的复杂性不会导致表处理速度明显加快，但可能会导致难以调试的错误。

    并行执行要求

    如果您想制作一个全局变化的素数列表以加快搜索速度，请停下来。我们正在讨论调整哈希表的大小。它们有很多，并且在不同的线程中工作。也就是说，为了计算新的素数并将其放入全局缓存中，需要保护该缓存免受竞争性访问。更改线程中的小表可能会因等待另一个线程中的大表找到其新大小的下一个百万素数而被延迟。这是令人不快的副作用。

    建议不要增加素数表。

    结论

    简单的根部搜索就解决了问题，代码很简单，运行时间是可以接受的（您无法通过执行此操作来看到分析方面的改进）。您甚至不必检查候选者甚至除数，因为这不会使代码过于复杂并改进常量。但不需要做任何其他事情，问题已经解决并且解决得很好了。

    • 0

相关问题