论坛 › C\C++交流 › 分享一个筛法求素数的代码

1121098405 发表于 2020-3-28 16:55:17

分享一个筛法求素数的代码

本帖最后由 1121098405 于 2020-4-8 12:14 编辑

我在虚拟机上运行找一亿以内的素数只用了0.6s左右
#include <stdlib.h>
#include <time.h>
#include <stdio.h>

unsigned int *get_primes(unsigned int size)
{
    unsigned int i, j, limit, *primes, max = size * 2 + 1;

    primes = (unsigned int *)malloc(sizeof(*primes) * size);

    for (i = 0; i < size; i++)
    {
      primes = i * 2 + 3;
    }

    for (i = 0; i < size; i++)
    {
      if (primes)
      {
            if (primes > (limit = max / primes))
                break;

            for (j = primes; j <= limit; j += 2)
            {
                primes[(primes * j - 3) / 2] = 0;
            }
      }
    }

    return primes;
}

void prime(unsigned int max)
{
    unsigned int *primes, count = 1, i, size = max / 2;
    clock_t start, stop;
    int duration;

    start = clock();
    primes = get_primes(size);
    stop = clock();
    duration = (int)((double)(stop - start) / CLOCKS_PER_SEC * 1000);

    for (i = 0; i < size; i++)
    {
      if (primes)
      {
            count++;
      }
    }

    free(primes);

    printf("在 %dms 内找到%u个质数\n", duration, count);
}

查看完整版本: 分享一个筛法求素数的代码