求100以?xún)?nèi)的所有素?cái)?shù)

求100以?xún)?nèi)的所有素?cái)?shù)什么是素?cái)?shù)?除0和1以外，只有1和它本?這兩個(gè)因數(shù)的數(shù)是素?cái)?shù)。如2，3，5，……第?種?法：??我們很容易找到1——10??的素?cái)?shù)：2，3，5，7。凡不是這4個(gè)數(shù)的倍數(shù)的數(shù)都為素?cái)?shù)。publicclassPrimeDemo{publicstaticvoidmain(String[]args){primeNumber();}publicstaticvoidprimeNumber(){intcount=4;StringBuildersb=newStringBuilder();sb.append(2+""+3+""+5+""+7+"");for(inti=10;i<=100;i++){if(i%2==0||i%3==0||i%5==0||i%7==0){continue;}else{sb.append(i+"");count++;}}System.out.println(count);System.out.println(sb.toString());}}第?種?法：根據(jù)素?cái)?shù)的定義：只有1和它本?這兩個(gè)因數(shù)的數(shù)稱(chēng)為素?cái)?shù)?？梢岳斫鉃椋?個(gè)數(shù)(n)，只要不能被[2，(n-1)]之間的數(shù)整除，那它就是?個(gè)素?cái)?shù)。以sqrt為分界點(diǎn)的原因：???先，因數(shù)是成對(duì)出現(xiàn)的。?如24,你找到個(gè)約數(shù)3,那么?定有個(gè)約數(shù)8,因?yàn)?4/3=8。然后，這對(duì)約數(shù)必須?個(gè)在根號(hào)n之前，?個(gè)在根號(hào)n之后。因?yàn)槎荚诟?hào)n之前的話(huà)，乘積?定?于n（根號(hào)nX根號(hào)n=n）。同樣，都在根號(hào)n之后的話(huà)，乘積?定?于n。所以，如果你在根號(hào)n之前都找不到因數(shù)的話(huà)，那么根號(hào)n之后就不會(huì)有了。//primeNumber();primeNumber2();}//根據(jù)素?cái)?shù)的定義找素?cái)?shù)publicstaticvoidprimeNumber(){intcount=0;inti;intj;for(i=2;i<=100;i++){for(j=2;j<=i-1;j++){if(i%j==0){break;}}if(j>=i){count++;System.out.print(i+"");}}System.out.println();System.out.println(count);}//============================優(yōu)化====================================/**外層循環(huán)代表被除數(shù)。由于1既不是質(zhì)數(shù)也不是合數(shù)，所以從2開(kāi)始*內(nèi)層循環(huán)代表除數(shù)。**/publicstaticvoidprimeNumber2(){intcount=0;StringBuildersb=newStringBuilder();for(inti=2;i<=100;i++){intj;intk=(int)Math.sqrt(i);for(j=2;j<=k;j++){if(i%j==0){break;}}if(j>k){count++;sb.append(i+"");}}System.out.println(count);System.out.println(sb.toString());}}第三種?法：??除2以外的所有偶數(shù)都不是素?cái)?shù)，因此可以篩選?半元素，剩下的數(shù)都為奇數(shù)。外層循環(huán)可篩選掉?半被除數(shù)。??奇數(shù)=奇數(shù)*奇數(shù)，它不可能被?個(gè)偶數(shù)整除。內(nèi)層循環(huán)可篩選掉?般除數(shù)。publicstaticvoidisPrime(){//2也為素?cái)?shù)StringBuildersb=newStringBuilder("2");intcount=1;//記錄素?cái)?shù)的個(gè)數(shù)。已經(jīng)有2這個(gè)素?cái)?shù)了，所以count的初始值為1for(inti=3;i<=100;i+=2){//從3開(kāi)始，以2為步長(zhǎng)，限定每個(gè)被除數(shù)都是奇數(shù)intj;booleanflag=true;//flag為true時(shí)，是素?cái)?shù)；為false時(shí)，是和數(shù)for(j=3;j<i;j+=2){//j從3開(kāi)始，以2為步長(zhǎng)，限定每個(gè)除數(shù)都是奇數(shù)。因?yàn)?個(gè)奇數(shù)是不可能被?個(gè)偶數(shù)整除的if(i%j==0){//如果i能夠被j整除flag=false;}}if(flag){count++;sb.append(i+"");}}System.out.println(count);System.out.println(sb.toString());}}第四種?法(埃拉托斯特尼篩法)：?具體步驟：1.先將1刪去(因?yàn)?不是素?cái)?shù))。2.?2去除它后?的各個(gè)數(shù)，把能被2整除的數(shù)刪掉，即把2的倍數(shù)刪掉。3.?3去除它后?的各數(shù)，把3的倍數(shù)刪掉。4.分別?5，7…各數(shù)作為除數(shù)去除這些數(shù)以后的各數(shù)。5.?直到sqrt(i)為?。然后重復(fù)上述步驟。??上述操作需要?個(gè)很?的容器去裝載所有數(shù)的集合，只要滿(mǎn)?上述條件，即2的倍數(shù)?于1的全部置0，3的倍數(shù)?于1的全部置0，4的倍數(shù)?于1的全部置0……?直到這個(gè)數(shù)據(jù)集合的末尾，這樣?來(lái)不為0的數(shù)就是素?cái)?shù)了，然后按下標(biāo)在??進(jìn)?查找。publicstaticvoidisPrime(){//默認(rèn)值為0，0——素?cái)?shù)；1——合數(shù)//這?寫(xiě)101是因?yàn)閿?shù)組的下標(biāo)是從0開(kāi)始的，?要求的是1——100之間的素?cái)?shù)int[]arr=newint[101];//0，1都不是素?cái)?shù)，標(biāo)記為1arr[0]=1;arr[1]=1;/**求1——100之間的素?cái)?shù)，把2的倍數(shù)過(guò)濾掉，3的倍數(shù)過(guò)濾掉，5的倍數(shù)過(guò)濾掉，7的倍數(shù)過(guò)濾掉，?直到sqrt(100)的倍數(shù)過(guò)慮掉（這*些都是2——sqrt(100)之間的素?cái)?shù)的倍數(shù)）**/for(inti=0;i<=Math.sqrt(100);i++){if(arr[i]==0){//for(intj=2*i;j<=100;j+=i){//可以從2*i修改成i*i,因?yàn)樵谇?的循環(huán)中從2——(i-1)的倍數(shù)都已經(jīng)驗(yàn)證過(guò)for(intj=i*i;j<=100;j+=i){arr[j]=1;}}}intcount=0;for(intx=0;