找素數是一項基本技能，方法也很多。在此，小編根據自己的經驗，總結一下我所知道的找素數的方法。
在此，我以找50以內的素數為例。
方法一
package sweet;
public class detached
{
?? ?public static void main(String[] args)
?? ?{
?? ?
?? ? //檬檬自己寫的普通方法求素數代碼
?? ? ??? ?int k = 0;
?? ??? ?System.out.println("50以內的素數分別為：");
?? ??? ?for (int i = 2; i <= 50; i++)
?? ??? ?{
?? ??? ??? ?for (int j = 2; j <= 25; j++)
?? ??? ??? ?{
?? ??? ??? ??? ?if (i % j == 0)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?if (j < i)
?? ??? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ??? ?if (j == i)
?? ??? ??? ??? ??? ??? ?System.out.print(i + " ");
?? ??? ??? ??? ??? ?break;
?? ??? ??? ??? ?}
?? ??? ??? ??? ?if (i % j != 0)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?if (j == 25)
?? ??? ??? ??? ??? ??? ?System.out.print(i + " ");
?? ??? ??? ??? ?}
?? ??? ??? ?}
?? ??? ?}
}
}分析：
已知1既不是素數，又不是合數，所以我們對50以內的數的判斷就只需要從2開始（有人會說，其實50以內的素數我都能背出來了，好像答案都很已知啊。檬檬只能說，這個時候我們不能鉆這種牛角尖，我們要試圖掌握一種通法）利用一個for循環，我們可以對每一個數進行判斷。最關鍵的也就是第二個for循環里面的內容了，它告訴我們如何對每一個數字進行素合數的判斷。
看第二個for循環的關鍵要素，第一個部分j = 2和第二個部分j <=25 。
有朋友就有疑問了，為什么j不能從0或1開始呢？我來為大家一一解答。首先，j不能等于0其實是很明顯的，看看我們后面的代碼，你會發現我們的j有什么身份，它是一個除數，在小學我們就知道，一個除數它是不能等于0的。那么，為什么j不能等于1呢？讓我們用反證法來說明。假設j從1開始，則對于外層循環中的任何一個數，它一進入內層for循環，就會執行break語句跳出內層循環。其最終的結果是，兩層循環下來，程序什么有意義的事情都沒有做。
那么，我們的j為什么要小于等于25呢？25有什么特別的含義嗎？當然有了，它是我們外層循環中循環變量上限值50的1/2。這個關系可就把兩個循環聯系在一起了?？墒沁@樣做的意義究竟是什么呢？這樣做其實是為了簡化循環。且聽我分析：一個合數，它除了可以寫成1和它本身的乘積之外，它還可以寫成另外兩個因數的乘積，而這另外兩個因數必定滿足：其中一個因數的值>=這個數的一半，另一個因數的值<=這個數的一半，所以，對于一個給定的數字，如果在這個數字的1/2以內的整數中，除了1以外沒有一個可以整除它，那個這個數就已經可以確定是一個素數了，而不再需要看它的后1/2的情況。舉個例子，已知17是一個素數，它的一半是8.5，那么小于等于8.5的所有整數分別是1、2、3、4、5、6、7、8，我們會發現，除了1以外沒有一個數可以整除17，根據我們上面的說法，這個時候就可以確定17是一個素數了，而不再需要看大于等于8.5的整數是否能整除17，而事實也確實如此，在大于等關于8.5的所有整數9、10、11、12、13、14、15、16、17中只有17可以整除17，而這個結果也符合17是個素數的結論。所以，我們只需要判斷到50的一半25就可以了。
在這個算法中，這種思想體現得并不是很淋漓盡致，只有在判斷50是否為素數的時候才嚴格用到這種思想，但在下一種算法中就體現得很深刻了。
回到我們的代碼，在第二個for循環中，我用了兩個大的if語句來分類判斷，當j可以整除i時，我們不能通過i有因數而直接否定它是素數，我們應該先判斷這個因數的值，如果這個因數是它本身的話，那么我們就說它也是素數（在i%j ==0這種情況下，i如果是素數的話，則這個因數j要么是1，要么是它本身，而我們已經證明這個因數不能為1，所以我們說在這種情況下，i是素數的充要條件就是i等于j），運用類似的辯證思維，如果j不能整除i，我們也不能立刻就說明i為素數，只有當j等于最后一個數25時，還是不能整除i，那么我們可以說明i真的是一個素數了。
這個算法的思路我自認為是很巧妙的，其中的反證、辯證思維體現得很充分，我覺得朋友們要是感興趣的話可以反復體會體會。
方法二
package sweet;
public class detached
{
?? ?public static void main(String[] args)
?? ?{
?? ??? ??? ? //小布老師給的求素數代碼
?? ??? ??? ? int m, n;// 變量n為要判斷的數字
?? ??? ?
?? ??? ??? ?System.out.println("50以內的素數有：");
?? ??? ??? ?A: for (n = 2; n <= 50; n++) {
?? ??? ??? ?for (m = 2; m <= n / 2; m++) {
?? ??? ??? ?if (n % m == 0)
?? ??? ??? ?continue A;
?? ??? ??? ?// 如果能被整除則變量n肯定不是素數，跳出內層循環
?? ??? ??? ?}
?? ??? ??? ?System.out.print(n + " " );//輸出素數
?? ??? ??? ?}
}
}這個代碼是我的老師給出的一個代碼，看起來更加地簡潔，也更加地實用。
它就非常充分地體現了我們上面談到的簡化循環的思想，關鍵語句m <=n/2，兩個循環之間建立起聯系。
素數2和3通過不進入內層循環的方式判斷出來，而其他的素數通過在它的數值前一半的所有整數中找不到它的因數來判斷。
方法三
package sweet;
public class detached
{
?? ?public static void main(String[] args)
?? ?{
?? ??? ?//檬檬自己寫的厄拉多塞篩選法求素數代碼
? ? ? ?//此處仍然是以求50以內的素數，所以我構造了一個“篩集”數組a，里面的數分別是從2到50的整數
?? ??? ?int []a = new int[49];
?? ??? ?for(int i0 = 0;i0<49;i0++)
?? ??? ?{
?? ??? ??? ?
?? ??? ??? ?a[i0]=i0+2;
?? ??? ?}
?? ??? ?
?? ??? ?int m = 2;
?? ??? ?int t ?= 0; ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? //m和t是兩個全局變量，t用于為“素數集”添加元素，m用于得到每一輪循環后產生的新素數
?? ??? ?int []sushumen = new int [49]; ? ? ? ? ? ? ? ?//我把表示“素數集”的數組的大小定義得和表示“篩集”的數組的大小一樣大，因為我的素數個數未知，而這是最相關最保險的一種定義方式
?? ??? ?
?? ??? ?
?? ??? ?
?? ??? ?for(int p = 0;p<49;p++)
?? ??? ?{
?? ??? ??? ?sushumen[t++] = m ;
?? ??? ??? ?a = delete(a,m);
?? ??? ??? ?m = number(a);
? ? ? ? ?if(m==0)break; //這一個判斷語句很關鍵。我們這里循環了49輪來找素數，是假設所判斷的49個數全部都是素數，事實上，素數的個數肯定是少于我們所判斷的個數的，所以依照我們這種賦0的方法，在某一輪結束之后，這個篩集中的數全部都是0，這個時候也恰恰可以作為循環結束的標志。
?? ??? ?}
?? ??? ?sushumen[t++] = m;
? ? ? ?//簡單的打印輸出
?? ??? ?System.out.println("50以內的素數分別為：");
?? ??? ?for(int p = 0;p<49;p++)
?? ??? ?{
if(sushumen[p]!=0)
?? ??? ??? ?System.out.print(sushumen[p]+" ");
?? ??? ?}
?? ?}
//函數number用于尋找到一個數組中第一個不為零的數，并返回（用于在篩集中刪除了某個數的倍數以后，找到產生的新素數。前提：在篩集中對某個數的倍數進行刪除時，并不是實實在在地把它從數組中刪除掉，而是將那個元素賦為0【這一點是可以改進的：如果哪位朋友知道了如何可放縮地刪除數組元素，就可以簡化這個步驟】）
?? ?public static int number(int a[])
?? ?{
?? ??? ?int b1 = 0;
?? ??? ?for(int b = 0;b<a.length;b++)
?? ??? ?{
?? ??? ??? ?if(a[b]!=0) { b1 = a[b];break;}
?? ??? ?}
?? ??? ?return b1;
?? ?}
//函數delete就是用來對一個數組刪除指定數m的倍數，實際上是將這個數的倍數所在的變量賦為0，然后返回這個數組
?? ?public static int[] delete(int a[],int m)
?? ?{
?? ??? ?for(int i = 0;i<a.length;i++)
?? ??? ?{
?? ??? ??? ?if(a[i]%m==0)a[i] = 0;
?? ??? ??? ?
?? ??? ?}
?? ??? ?return a;
?? ?}
}
}這個代碼是我在只看了厄拉多塞篩選法的算法解析后，根據自己的理解打出來的，因為我想對比一下自己的代碼和教材中給出的代碼。結果是基于相同的思想，我們的具體實現過程也挺不同的，這種不同是真的有趣。
知識普及：厄拉多塞篩選法求素數
厄拉多塞是古希臘的一名科學家。且n以內的素數的思想是，首先將2~n的數放入一個集合（篩集），將已知的最小素數2放入素數集，再去掉篩集中所有2的倍數后，篩集中的最小值3即為新找到的素數，再去掉篩集中所有3的倍數，篩集中的最小數5即為新找到的素數。依法執行下去，直到篩集為空時，素數集中得到數就是我們要找的全部素數。
方法四
package sweet;
public class detached
{
?? ?public static void main(String[] args)
?? ?{
//教材上的原版厄拉多塞篩選法代碼
int maxNumber = 50;//命令行參數，獲取素數的范圍(教材int maxNumber = Integer.parseInt(args[0]);)
?? ??? ?int arraySize = maxNumber/3;//素數集的大小
?? ??? ?int primeNo[] = new int [arraySize];//素數集合
?? ??? ?int index,num,i,primeCount;
?? ??? ?primeNo[0] = 2; ? ? //把第一個素數放入素數集合
?? ??? ?primeCount = 1; ? ? //素數的個數
?? ??? ?index = 1;//下一個素數存放的位置
?? ??? ?num = 3;//測試數，從奇數開始測試，偶數不需要測試
?? ??? ?
?? ??? ?
?? ??? ?do
?? ??? ?{
?? ??? ??? ?i = 0; ? //素數集合上的循環變量
?? ??? ??? ?while(i<primeCount && (num % primeNo[i]!=0))//用素數集合中的數測試num
?? ??? ??? ??? ?i++;
?? ??? ??? ?if(i==primeCount) ? ?//num是素數
?? ??? ??? ?{
?? ??? ??? ??? ?primeNo[index] = num; ? //把num放入到素數集中
?? ??? ??? ??? ?index++; ? ? ? ? ? ? ? ? //下標遞增
?? ??? ??? ??? ?primeCount++; ? ? ? ? ? ?//素數個數增加
?? ??? ??? ?}
?? ??? ??? ?num+=2; ? ? ? ? ? ? ? ? ? ? ?//測試下一個數
?? ??? ?
?? ??? ?}while(num<maxNumber);
?? ??? ?
?? ??? ?//打印輸出
?? ??? ?System.out.println("50以內的素數：");
?? ??? ?for(i = 0;i<primeCount;i++)
?? ??? ?{
?? ??? ??? ?System.out.print(" "+primeNo[i]);
?? ??? ??? ?if((i+1)%10==0) ? System.out.println();
?? ??? ??? ??? ?
?? ??? ?}
?? ??? ??? ??? ?System.out.println();
?? ??? ??? ??? ?System.out.println("素數個數："+primeCount);
?? ?}
}方法四的優點：1、它進一步簡化了循環，因為它只測試了奇數2、它設計了一個控制格式的語句
