快捷導(dǎo)航

C/C++判斷素?cái)?shù)的三種方法

更新時(shí)間：2023年12月19日 10:01:52 作者：釋懷、過客。

這篇文章主要給大家介紹了C/C++判斷素?cái)?shù)的三種方法,常規(guī)的函數(shù)判斷法,埃氏篩法和歐拉篩法這三種方法,并通過代碼示例講解的非常詳細(xì),具有一定的參考價(jià)值,需要的朋友可以參考下

1.常規(guī)的函數(shù)判斷法

假如題目是我們要求 1~n之間的素?cái)?shù)并打印出來，我們可以寫如下函數(shù)：

int prime(int i) // 求是否為素?cái)?shù)需要考慮1，2兩種情況
{
    if (i == 1) return 0;
    if (i == 2) return 1;
    for (int j = 2; j * j <= i; ++j)
        if (i % j == 0)//如果遇到j(luò)是i的因數(shù)，i就不是質(zhì)數(shù)，返回0
            return 0;
    return 1;//沒有找到這個(gè)數(shù)的因數(shù)就返回1
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        if (prime(i))
            printf("%d ", i);
    return 0;
}

2.埃氏篩法

我們?cè)谟變簣@就學(xué)過合數(shù)是除了能被1和它本身整除，還能被其他的正整數(shù)整除的數(shù)，然而合數(shù)還有如下定義：當(dāng)一個(gè)數(shù)可以被素?cái)?shù)之乘積表示時(shí)，它被稱為合數(shù)。這是基本定理算術(shù)，也被稱為唯一素因數(shù)分解定理。這個(gè)定理表明任何一個(gè)大于1的整數(shù)都可以被唯一地分解成素?cái)?shù)的乘積。

埃氏篩核心思想就是 從第一個(gè)沒有被篩除過數(shù)（num）的開始，在給定的范圍內(nèi)依次篩去num的倍數(shù)，例如，num=2,我們可以依次篩去4，6，8......;對(duì)于，num=n，依次篩除 k*n(k=1,2,3...)；

代碼實(shí)現(xiàn)：

int pri[10000001];
int main()
{ 
    int n;
    scanf("%d",&n);
    for(int i = 2; i*i <= n; i++)//埃氏篩   時(shí)間復(fù)雜度接近于線性（n*lnln(n))
	{
		if(pri[i] == 0)
		{
			for(int j = i * i; j <= n; j += i)
			    pri[j] = 1; // j是i的一個(gè)倍數(shù)，則j是合數(shù)，篩掉。
		}
        
}

3.歐拉篩

這是對(duì)埃氏篩的優(yōu)化，埃氏篩法在執(zhí)行時(shí)可能會(huì)對(duì)同一個(gè)數(shù)進(jìn)行多次篩除

比如num=120 會(huì)在i=（2，3，4，6......）的時(shí)候分別篩除一次，而且數(shù)越大會(huì)被篩除的次數(shù)越多，就造成了很大的時(shí)間浪費(fèi)

而歐拉篩的核心思想就是確保每個(gè)合數(shù)只被最小質(zhì)因數(shù)篩掉。

代碼實(shí)現(xiàn)：

int vis[10000001];
int pri[10000001];
int main()
{ 
    int n=10000,m=0,cnt=0;
 
    for (int i = 2; i <= n; i ++ )//歐拉篩 時(shí)間復(fù)雜度基本為O（n）
    {
        if (vis[i] == 0) pri[cnt ++ ] = i;//將質(zhì)數(shù)存到pri中
        for (int j = 0; pri[j] * i <= n; j ++ )//要確保當(dāng)前質(zhì)數(shù)的i倍小于等于n。
        {
            vis[pri[j] * i] = 1;
           
            if (i % pri[j] == 0) break;//終止條件（當(dāng)前數(shù)i遇到了它的最小質(zhì)因數(shù)）
        }
    }
     
 
    return 0;
}

以上就是C/C++判斷素?cái)?shù)的三種方法的詳細(xì)內(nèi)容，更多關(guān)于C/C++判斷素?cái)?shù)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: