C语言求素数(质数)的算法

C语言求素数(质数)的算法

前言

上次被出了一题质数的C语言求解题目（  ），当时用了最粗暴的算法，回来仔细参考资料，其实答案有很多种：

1，小学生版本：

判断 x 是否为质数，就从 2 一直算到 x-1。

static rt_uint32_t array1[ARRAY_LEN];
void func1(void)
{
    for (rt_uint32_t i = 1; i <= ARRAY_LEN; i++)
    {
        array1[i - 1] = 0;
    }

    rt_uint32_t x, y = 0, z = 0;
    rt_uint32_t i = 0;
    for (x = 2; x <= ARRAY_LEN; x++)
    {
        y = 0;
        for (i = 1; i <= x; i++)
        {
            if (x % i == 0)
            {
                y++;
            }
        }
        if (y == 2)
        {
            z++;
            array1[x - 1] = x;
        }
    }
    array1[0] = 1;
}

2，小学生毕业版：

x 如果有质因数，肯定会小于等于 x/2，所以捏，就从 2 一直到 x/2 即可。

static rt_uint32_t array2[ARRAY_LEN];
void func2(void)
{
    for (rt_uint32_t i = 1; i <= ARRAY_LEN; i++)
    {
        array2[i - 1] = 0;
    }

    rt_uint32_t x, y = 0, z = 0;
    rt_uint32_t i = 0;
    for (x = 3; x <= ARRAY_LEN; x++)
    {
        y = 0;
        for (i = 2; i <= x / 2; i++)
        {
            if (x % i == 0)
            {
                y++;
                break;
            }
        }
        if (y == 0)
        {
            z++;
            array2[x - 1] = x;
        }
    }
    array2[0] = 1;
    array2[1] = 2;
}

更多详情见请继续阅读下一页的精彩内容：