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

1121098405

我在虚拟机上运行找一亿以内的素数只用了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] = i * 2 + 3;
    }

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

            for (j = primes[i]; j <= limit; j += 2)
            {
                primes[(primes[i] * 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[i])
        {
            count++;
        }
    }

    free(primes);

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