前言

哈嘍各位友友們，我今天又學(xué)到了很多有趣的知識(shí)，現(xiàn)在迫不及待的想和大家分享一下！我僅已此文，手把手帶領(lǐng)大家探討利用試除法、篩選法求解素?cái)?shù)的n層境界！都是精華內(nèi)容，可不要錯(cuò)過(guò)喲！！！

必備小知識(shí)

質(zhì)數(shù)又稱素?cái)?shù)。一個(gè)大于1的自然數(shù)，除了1和它自身外，不能被其他自然數(shù)整除的數(shù)叫做質(zhì)數(shù)；否則稱為合數(shù)（規(guī)定1既不是質(zhì)數(shù)也不是合數(shù)）。這里以求解100~200之間的素?cái)?shù)舉例講解

C語(yǔ)言詳解《試除法》求解素?cái)?shù)

試除法境界1

境界1實(shí)現(xiàn)思路分析：?

• 首先，利用第一層for循環(huán)產(chǎn)生100~200的整數(shù)；
• 其次，利用第二層for循環(huán)產(chǎn)生2~ i - 1之間的整數(shù)，并讓100到200之間的每一個(gè)數(shù)和2到 i - 1之間的整數(shù)試除。
• 定義flag變量，若flag為0，則不是素?cái)?shù)；若flag為1，則是素?cái)?shù)。
• 定義count變量，記錄試除次數(shù)。
• 境界1算法的理性分析：境界1，簡(jiǎn)單來(lái)說(shuō)就是讓每一個(gè)數(shù)i和2~ i-1的數(shù)試除，這是最簡(jiǎn)單的想法，但是算法的效率是最低的~

看了文字的描述，大家可能理解的還是不夠深刻。這里俺親自敲出代碼輔助大家理解~?

境界1源碼：?

#include<stdio.h>
int main()
{
    
    int count = 0;//記錄試除次數(shù)
    int i = 0;
    int j = 0;
    for (i = 100; i <= 200; i++)
    {
        int flag = 1;//flag最終結(jié)果為1，表示i是素?cái)?shù)，為0表示不是素?cái)?shù)。
        for (j = 2; j < i; j++)
        {
            count++;
            if (i % j == 0)
            {
                flag = 0;
                break;
            }

        }
        if(flag == 1)
        printf("%d ", i);
    }
    printf("\n境界1試除總次數(shù)：%d", count);
    return 0;
}

代碼結(jié)果運(yùn)行圖：?

由境界1求解100~200之間的素?cái)?shù)，需要試除3292次！！！可見(jiàn)其算法效率如何啦。

試除法境界2

境界2實(shí)現(xiàn)思路分析：?

• 首先利用第一層for循環(huán)產(chǎn)生101~199的整數(shù)，這是和境界1最本質(zhì)的區(qū)別！為什么這樣設(shè)計(jì)呢？原因很簡(jiǎn)單，因?yàn)?00到200之間的偶數(shù)一定不是素?cái)?shù)，可以不用參與試除過(guò)程。
• 其次，利用第二層for循環(huán)產(chǎn)生2~ i - 1之間的整數(shù)，并讓101到199之間的每一個(gè)數(shù)和2到 i -1之間的整數(shù)試除。
• 定義flag變量，若flag為0，則不是素?cái)?shù)；若flag為1，則是素?cái)?shù)。
• 定義count變量，記錄試除次數(shù)。
• 境界2算法的理性分析：境界2和境界1類似，就是讓每一個(gè)數(shù)i和2~ i-1的數(shù)試除，但是境界2能夠提前讓一些本不可能是素?cái)?shù)的整數(shù)（100—200間的偶數(shù)）提前排除掉~(yú)

境界2源碼：?

#include<stdio.h>
int main()
{
    
    int count = 0;//記錄試除次數(shù)
    int i = 0;
    int j = 0;
    for (i = 101; i < 200; i+=2)//提前排除100到200之間的偶數(shù)，符合這個(gè)條件一定不是素?cái)?shù)。
    {
        int flag = 1;//flag最終結(jié)果為1，表示i是素?cái)?shù)，為0表示不是素?cái)?shù)。
        for (j = 2; j < i; j++)
        {
            count++;
            if (i % j == 0)
            {
                flag = 0;
                break;
            }

        }
        if(flag == 1)
        printf("%d ", i);
    }
    printf("\n境界2試除總次數(shù)：%d", count);
    return 0;
}

代碼結(jié)果運(yùn)行圖：?

由境界2求解100~200之間的素?cái)?shù)，需要試除3241次，稍微比境界1好那么一丟丟啦！但是其算法效率還是不盡人意。

試除法境界3

境界3實(shí)現(xiàn)思路分析：

• 首先，利用第一層for循環(huán)產(chǎn)生100~200的整數(shù)；
• 其次，利用第二層for循環(huán)產(chǎn)生2~ sqrt（i）之間的整數(shù)，并讓101到199之間的每一個(gè)數(shù)和2到 sqrt（i）之間的整數(shù)試除。為什么這樣設(shè)計(jì)呢？設(shè)計(jì)思路分析：因?yàn)槿魏我粋€(gè)不是素?cái)?shù)的數(shù)即合數(shù)，都一定可以進(jìn)行因式分解。這里已16舉例說(shuō)明，16 = 2 * 8 = 4 * 4 。因此如果16被2整除就可以判定16不是素?cái)?shù)了，就不用那2到 i - 1的每一個(gè)數(shù)都試除一遍啦。 因此，只需要拿2 ~sqrt（i）的數(shù)試除即可，這樣大大提高了算法的效率！
• 定義flag變量，若flag為0，則不是素?cái)?shù)；若flag為1，則是素?cái)?shù)。
• 定義count變量，記錄試除次數(shù)。
• 境界3算法的理性分析：境界3相比于前面兩種境界，做了很大的改進(jìn)！讓每一個(gè)數(shù)試除的測(cè)試減少了至少一半，大大減少了試除的次數(shù)，從而大大提高了算法的效率！！！

境界3源碼：?

#include<stdio.h>
#include<math.h>
int main()
{

	int count = 0;//記錄試除次數(shù)
	int i = 0;
	int j = 0;
	for (i = 100; i <= 200; i++)
	{
		int flag = 1;//flag最終結(jié)果為1，表示i是素?cái)?shù)，為0表示不是素?cái)?shù)。
		for (j = 2; j <= sqrt(i); j++)//只需要試除2到sqrt(i)之間的整數(shù)即可
		{
			count++;
			if (i % j == 0)
			{
				flag = 0;
				break;
			}

		}
		if (flag == 1)
			printf("%d ", i);
	}
	printf("\n境界3試除總次數(shù)：%d", count);
	return 0;
}

代碼結(jié)果運(yùn)行圖：?

由境界4求解100~200之間的素?cái)?shù)，只需要試除393次，相比于境界1和境界2的算法效率來(lái)說(shuō)，已經(jīng)有長(zhǎng)足的改進(jìn)啦！

試除法境界4

境界4實(shí)現(xiàn)思路分析：

• 首先，采用境界2的算法思想。利用第一層for循環(huán)產(chǎn)生101~199的整數(shù)。
• == 其次，利用境界三的試除想法，拿2 ~sqrt（i）的數(shù)試除。==
• 定義flag變量，若flag為0，則不是素?cái)?shù)；若flag為1，則是素?cái)?shù)。
• 定義count變量，記錄試除次數(shù)。
• 境界4算法的理性分析：境界4相比于境界3，再做優(yōu)化！先排除掉偶數(shù)。

境界4源碼：?

#include<stdio.h>
#include<math.h>
int main()
{

	int count = 0;//記錄試除次數(shù)
	int i = 0;
	int j = 0;
	for (i = 101; i < 200; i += 2)//排除100到200之間的2的倍數(shù)，符合這個(gè)條件一定不是素?cái)?shù)。
	{
		int flag = 1;//flag最終結(jié)果為1，表示i是素?cái)?shù)，為0表示不是素?cái)?shù)。
		for (j = 2; j <= sqrt(i); j++)//只需要試除2到sqrt(i)之間的整數(shù)即可
		{
			count++;
			if (i % j == 0)
			{
				flag = 0;
				break;
			}

		}
		if (flag == 1)
			printf("%d ", i);
	}
	printf("\n境界4試除總次數(shù)：%d", count);
	return 0;
}

代碼結(jié)果運(yùn)行圖：?

由境界4求解100~200之間的素?cái)?shù)，試除總次數(shù)為342，是,綜合考慮了境界2和境界3的改良思想，已經(jīng)達(dá)到了試除法的最高境界啦！

C語(yǔ)言詳解《篩選法》求解素?cái)?shù)

預(yù)備小知識(shí)

埃拉托色尼是一名古希臘的地理學(xué)家，他是世界上第一個(gè)計(jì)算出地球周長(zhǎng)的人。埃拉托色尼素?cái)?shù)篩選法可以很快速的計(jì)算出1到N之間的所有素?cái)?shù)。埃拉托色尼素?cái)?shù)篩選法大概的計(jì)算思路是：將n開(kāi)根號(hào)，即N^0.5 ，去掉2到N^0.5中所有素?cái)?shù)的倍數(shù)，剩下的數(shù)便都是素?cái)?shù)了。例如求1到25中的素?cái)?shù)有哪些，第一步是將25開(kāi)根號(hào)，得到5；第二步將2到5的素?cái)?shù)取出來(lái)，分別是2、3、5:再將2到25中且是2、3、5的倍數(shù)的數(shù)去掉，即去掉4、6、8、9、10、12、14、15、16、18、 20、21、22、24、25；剩下2、3、5、7、11、13、17、19便是1到25中的所有素?cái)?shù)了。從上面我們可以看出篩選法和試除法其實(shí)有著本質(zhì)上的區(qū)別，試除法是判斷每一個(gè)數(shù)是不是素?cái)?shù)來(lái)達(dá)到目的；而篩選法不是如此，篩選法是將不是素?cái)?shù)的數(shù)全部去除，然后得到余下的數(shù)來(lái)達(dá)到目的~

境界5（基礎(chǔ)篩選法）實(shí)現(xiàn)思路分析：

• 首先，找到最小的質(zhì)數(shù)2，再把范圍內(nèi)的所有2的倍數(shù)去掉；然后接下來(lái)找次小的質(zhì)數(shù)3,再把所有3的倍數(shù)去掉；接著往復(fù)篩選去除，剩下的那些就全是素?cái)?shù)啦！
• 這里需要設(shè)計(jì)一個(gè)數(shù)組，只要滿足上述這些步驟，即將大于1的且是2、3、4…的倍數(shù)全部置為0。最終不是0的數(shù)就是所謂的素?cái)?shù)啦！

篩選法境界5

境界5源碼：?

#include<stdio.h>
int main()
{
    int i = 0;
    int j = 0;
    int arr[100];
    int count = 0;
    for (i = 0; i < 100; i++)
    {
        arr[i] = 100 + i;//將數(shù)組先初始化存儲(chǔ)100到199。
                        //沒(méi)有存儲(chǔ)200也沒(méi)關(guān)系，200一定不是素?cái)?shù)
        
    }
    for (i = 0; i < 100; i++)
    {
        j = i + 1;
        while (j > 1)
        {
            count++;
            if (arr[i] % j == 0)
                arr[i] = 0;
            j = j - 1;
        }
    }
    for (j = 1; j < 100; j++)
    {
        if (arr[j] != 0)
        {
            printf("%d ", arr[j]);
        }
    }
    return 0;
}

代碼結(jié)果運(yùn)行圖：?