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