求100以內(nèi)的所有素數(shù)

求100以內(nèi)的所有素數(shù)什么是素數(shù)?除0和1以外，只有1和它本?這兩個因數(shù)的數(shù)是素數(shù)。如2，3，5，……第?種?法：??我們很容易找到1——10??的素數(shù)：2，3，5，7。凡不是這4個數(shù)的倍數(shù)的數(shù)都為素數(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ù)素數(shù)的定義：只有1和它本?這兩個因數(shù)的數(shù)稱為素數(shù)?？梢岳斫鉃?，?個數(shù)(n)，只要不能被[2，(n-1)]之間的數(shù)整除，那它就是?個素數(shù)。以sqrt為分界點(diǎn)的原因：???先，因數(shù)是成對出現(xiàn)的。?如24,你找到個約數(shù)3,那么?定有個約數(shù)8,因為24/3=8。然后，這對約數(shù)必須?個在根號n之前，?個在根號n之后。因為都在根號n之前的話，乘積?定?于n（根號nX根號n=n）。同樣，都在根號n之后的話，乘積?定?于n。所以，如果你在根號n之前都找不到因數(shù)的話，那么根號n之后就不會有了。//primeNumber();primeNumber2();}//根據(jù)素數(shù)的定義找素數(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開始*內(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ù)都不是素數(shù)，因此可以篩選?半元素，剩下的數(shù)都為奇數(shù)。外層循環(huán)可篩選掉?半被除數(shù)。??奇數(shù)=奇數(shù)*奇數(shù)，它不可能被?個偶數(shù)整除。內(nèi)層循環(huán)可篩選掉?般除數(shù)。publicstaticvoidisPrime(){//2也為素數(shù)StringBuildersb=newStringBuilder("2");intcount=1;//記錄素數(shù)的個數(shù)。已經(jīng)有2這個素數(shù)了，所以count的初始值為1for(inti=3;i<=100;i+=2){//從3開始，以2為步長，限定每個被除數(shù)都是奇數(shù)intj;booleanflag=true;//flag為true時，是素數(shù)；為false時，是和數(shù)for(j=3;j<i;j+=2){//j從3開始，以2為步長，限定每個除數(shù)都是奇數(shù)。因為?個奇數(shù)是不可能被?個偶數(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刪去(因為1不是素數(shù))。2.?2去除它后?的各個數(shù)，把能被2整除的數(shù)刪掉，即把2的倍數(shù)刪掉。3.?3去除它后?的各數(shù)，把3的倍數(shù)刪掉。4.分別?5，7…各數(shù)作為除數(shù)去除這些數(shù)以后的各數(shù)。5.?直到sqrt(i)為?。然后重復(fù)上述步驟。??上述操作需要?個很?的容器去裝載所有數(shù)的集合，只要滿?上述條件，即2的倍數(shù)?于1的全部置0，3的倍數(shù)?于1的全部置0，4的倍數(shù)?于1的全部置0……?直到這個數(shù)據(jù)集合的末尾，這樣?來不為0的數(shù)就是素數(shù)了，然后按下標(biāo)在??進(jìn)?查找。publicstaticvoidisPrime(){//默認(rèn)值為0，0——素數(shù)；1——合數(shù)//這?寫101是因為數(shù)組的下標(biāo)是從0開始的，?要求的是1——100之間的素數(shù)int[]arr=newint[101];//0，1都不是素數(shù)，標(biāo)記為1arr[0]=1;arr[1]=1;/**求1——100之間的素數(shù)，把2的倍數(shù)過濾掉，3的倍數(shù)過濾掉，5的倍數(shù)過濾掉，7的倍數(shù)過濾掉，?直到sqrt(100)的倍數(shù)過慮掉（這*些都是2——sqrt(100)之間的素數(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,因為在前?的循環(huán)中從2——(i-1)的倍數(shù)都已經(jīng)驗證過for(intj=i*i;j<=100;j+=i){arr[j]=1;}}}intcount=0;for(intx=0;