C語言素?cái)?shù)的判定

幾種簡單的判斷素?cái)?shù)的方法2009年05月12日星期二下午10:34素?cái)?shù)還有很多東西需要學(xué)，先整理三種最簡單的判斷素?cái)?shù)的方法，以后再深究補(bǔ)充。判斷n是否為素?cái)?shù)1、最簡單的方法用n除以2-sqrt(n),有一個(gè)能除盡就不是素?cái)?shù)，否則是素?cái)?shù)。時(shí)間復(fù)雜度：O(sqrt(n))2、 素?cái)?shù)判斷法：這種方法是對(duì)上面方法的改進(jìn)，上面方法是對(duì)2-sqrt(n)之間的數(shù)進(jìn)行判斷是否能除盡，而因?yàn)橛腥缦滤阈g(shù)基本定理，可以減少判斷量。算術(shù)基本定理：又稱為素?cái)?shù)的唯一分解定理，即：每個(gè)大于1的自然數(shù)均可寫為素?cái)?shù)的積，而且這些素因子按大小排列之后，寫法僅有一種方式。例如:6936=2^3X3X17^2,1200=2"4X3X5“2。由算術(shù)基本定理知，任何合數(shù)都可分解為一些素?cái)?shù)的乘積，所以判斷一個(gè)數(shù)能不能被2-sqrt(n)之間的素?cái)?shù)整除即可。但是必須知道2-sqrt(n)之間的所有素?cái)?shù)。3、 篩選法這種方法可以找出一定范圍內(nèi)的所有的素?cái)?shù)。思路是，要求10000以內(nèi)的所有素?cái)?shù)，把1-10000這些數(shù)都列出來，1不是素?cái)?shù)，劃掉；2是素?cái)?shù)，所有2的倍數(shù)都不是素?cái)?shù)，劃掉；取出下一個(gè)幸存的數(shù)，劃掉它的所有倍數(shù)；直到所有幸存的數(shù)的倍數(shù)都被壞掉為止。要找出10000以為的所有的素?cái)?shù)，則需要一個(gè)大小為10000的數(shù)組,將其所有元素設(shè)置為未標(biāo)記首先把1設(shè)置為標(biāo)記，從2開始，標(biāo)記所有是它倍數(shù)的數(shù)，然后對(duì)下一個(gè)沒有標(biāo)記的數(shù)進(jìn)行標(biāo)記它的倍數(shù)。當(dāng)標(biāo)記完成后，所有未標(biāo)記的數(shù)即為素?cái)?shù)。這種算法需要O(n)的空間，不要偶數(shù)，可以節(jié)省一半的存儲(chǔ)空間，標(biāo)記需要0(n'2/logn)(我寫的，不知道對(duì)不對(duì))，判斷是否是素?cái)?shù)只需要0(1)的時(shí)間。貼一下程序代碼：/*2009.5.12byHK*/#include<stdio.h>#include<math.h>#include<string.h>inta[10000];//100以內(nèi)的素?cái)?shù)intprime100[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,};/************************************************************************//*第一種方法：最簡單的方法*//************************************************************************/intis_prime1(intn){if(n%2==0)return0;for(inti=3;i<=sqrt((double)n);i+=2)if(n%i==0)return0;return1;}/************************************************************************//*第二種方法：素?cái)?shù)判斷法*//* 若判斷10000以內(nèi)的數(shù)，需要知道100以內(nèi)的所有素?cái)?shù)*//************************************************************************/intis_prime2(intn){inti;for(i=0;i<25;i++)if(n%prime100[i]==0)return0;return1;/************************************************************************//*第三種方法：篩選法，打素?cái)?shù)表，然后判斷*//************************************************************************///篩選,a[i]=O,i為素?cái)?shù)voidcreate_table()inti,tmp;memset(a,O,sizeof(a));a[O]=1;a[1]=1;for(i=2;i<1OOOO;i++){if(!a[i]){tmp=i*2;;while(tmp<1OOOO){a[tmp]=1;tmp+=i;}}}intis_prime3(intn){return!a[n];}intmain(){intnum,res;create_table();printf("Inputthenum:");scanf("%d",&num);

res=is_pri