C語言求素數(質數)的算法

前言

上次被出了一題質數的C語言求解題目（ http://www.linuxidc.com/Linux/2014-06/103097.htm ），當時用了最粗暴的算法，回來仔細參考資料，其實答案有很多種：

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;
}

更多詳情見請繼續閱讀下一頁的精彩內容： http://www.linuxidc.com/Linux/2014-06/103100p2.htm