最后一次是出了素數的問題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;

}

3，初中生版：

除了2以外的質因數都是奇數。

所以算從3開始一直到 x/2 的全部奇數。

static rt_uint32_t array3[ARRAY_LEN];

void func3(void)

{

for (rt_uint32_t i = 1; i <= ARRAY_LEN; i++)

{

array3[i - 1] = 0;

}

rt_uint32_t x, y = 0, z = 0;

rt_uint32_t i = 0;

for (x = 3; x <= ARRAY_LEN; x += 2)

{

y = 0;

for (i = 2; i <= x / 2; i++)

{

if (x % i == 0)

{

y++;

break;

}

}

if (y == 0)

{

z++;

array3[x - 1] = x;

}

}

array3[0] = 1;

array3[1] = 2;

}

4，高中生版：

事實上僅僅要從 2 一直嘗試到根號x。就能夠了。由于x僅僅要有因數必然有一個因數小于等于根號x。

static rt_uint32_t array4[ARRAY_LEN];

void func4(void)

{

for (rt_uint32_t i = 1; i <= ARRAY_LEN; i++)

{

array4[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 <= sqrt(x); i++)

{

if (x % i == 0)

{

y++;

break;

}

}

if (y == 0)

{

z++;

array4[x - 1] = x;

}

}

array4[0] = 1;

array4[1] = 2;

}

5，本科生版：

把上面的版本號都綜合起來

static rt_uint32_t array5[ARRAY_LEN];

void func5(void)

{

for (rt_uint32_t i = 1; i <= ARRAY_LEN; i++)

{

array5[i - 1] = 0;

}

rt_uint32_t x, y = 0, z = 0;

rt_uint32_t i = 0;

for (x = 3; x <= ARRAY_LEN; x += 2)

{

y = 0;

for (i = 2; i <= sqrt(x); i++)

{

if (x % i == 0)

{

y++;

break;

}

}

if (y == 0)

{

z++;

array5[x - 1] = x;

}

}

array5[0] = 1;

array5[1] = 2;

}

6。本科生畢業版本號：

就是當i是質(素)數的時候，i的全部的倍數必定是合數。

假設i已經被推斷不是質數了，那么再找到i后面的質數來把這個質

數的倍數篩掉。

static rt_uint32_t array6[ARRAY_LEN];

void func6(void)

{

for (rt_uint32_t i = 1; i <= ARRAY_LEN; i += 2)

{

array6[i - 1] = i;

}

for (rt_uint32_t i = 3; i < sqrt(ARRAY_LEN); i+=2)

{

if (array6[i-1])

{

for(rt_uint32_t j=i<<2;j<=ARRAY_LEN;j+=i)

{

array6[j] = 0;

}

}

}

array6[1] = 2;

}

總結

分析了6個算法在我的嵌入式平臺執行結果：

定義ARRAY_LEN = 1000；

func1

2513922

func2

221563

func3

213926

func4

762945

func5

674993

func6

14663

我們能夠看到func4、func5并沒有我們想象的那么節省時間，我想問題主要出在sqrt上面；sqrt本身是比較耗時的計算，然后func4與func5調用sqrt的次數又比較多；所以導致結果不太樂觀。

當然假設把ARRAY_LEN調大。可能結果又會不一樣

至此，也就僅僅是我本科畢業的水準了，后面還有更好的純C算法可以告訴我。

總結

以上是生活随笔為你收集整理的c语言的求素数算法,C语言求素数的算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。