1。自然數(shù)是0，1，2……
2。素數(shù)是2，3，5……（不包括1的只能背1和它本身整除的自然數(shù)）

public class Test
{
?/*
? * 最普通的算法：
? * 打印num以內(nèi)的素數(shù)并返回素數(shù)個數(shù)
? * n、m分別為外、內(nèi)層循環(huán)，i是第幾個素數(shù)，s是素數(shù)個數(shù)
? */
?public int prime(int num){
??int n,m,i=0,s=0;
??label1:
??for(n=2;n<=num;n++)
??{
???for(m=2;m<=n/2;m++)
???{
????if(n%m==0)
????continue label1;
???}
???s++;
???i++;
???System.out.println("第"+i+"個素數(shù)是："+n);
??}
??return s;
?}
?
?public static void main(String args[]){
??Test test = new Test();
??int sum = test.prime(1000);
??System.out.println("共"+sum+"個素數(shù)");
?}
}

【1】求10000以內(nèi)的所有素數(shù)。
素數(shù)是除了1和它本身之外再不能被其他數(shù)整除的自然數(shù)。由于找不到一個通項公式來表示所有的素數(shù)，所以對于數(shù)學家來說，素數(shù)一直是一個未解之謎。像著名的 哥德巴赫猜想、孿生素數(shù)猜想，幾百年來不知吸引了世界上多少優(yōu)秀的數(shù)學家。盡管他們苦心鉆研，嘔心瀝血，但至今仍然未見分曉。
自從有了計算機之后，人們借助于計算機的威力，已經(jīng)找到了2²¹⁶⁰⁹¹以內(nèi)的所有素數(shù)。
求素數(shù)的方法有很多種，最簡單的方法是根據(jù)素數(shù)的定義來求。對于一個自然數(shù)N，用大于1小于N的各個自然數(shù)都去除一下N，如果都除不盡，則N為素數(shù)，否則N為合數(shù)。
但是，如果用素數(shù)定義的方法來編制計算機程序，它的效率一定是非常低的，其中有許多地方都值得改進。
第一，對于一個自然數(shù)N，只要能被一個非1非自身的數(shù)整除，它就肯定不是素數(shù)，所以不
必再用其他的數(shù)去除。
第二，對于N來說，只需用小于N的素數(shù)去除就可以了。例如，如果N能被15整除，實際
上就能被3和5整除，如果N不能被3和5整除，那么N也決不會被15整除。
第三，對于N來說，不必用從2到N一1的所有素數(shù)去除，只需用小于等于√N(根號N)的所有素數(shù)去除就可以了。這一點可以用反證法來證明：
如果N是合數(shù)，則一定存在大于1小于N的整數(shù)d1和d2，使得N=d1×d2。
如果d1和d2均大于√N，則有：N＝d1×d2>√N×√N＝N。
而這是不可能的，所以，d1和d2中必有一個小于或等于√N。
基于上述分析，設計算法如下：
(1)用2，3，5，7逐個試除N的方法求出100以內(nèi)的所有素數(shù)。
(2)用100以內(nèi)的所有素數(shù)逐個試除的方法求出10000以內(nèi)的素數(shù)。
首先，將2，3，5，7分別存放在a[1]、a[2]、a[3]、a[4]中，以后每求出一個素數(shù)，只要不大于100，就依次存放在A數(shù)組中的一個單元 中。當我們求100—10000之間的素數(shù)時，可依次用a[1]－a[2]的素數(shù)去試除N，這個范圍內(nèi)的素數(shù)可以不保存，直接打印。

【2】用篩法求素數(shù)。
簡單介紹一下厄拉多塞篩法。厄拉多塞是一位古希臘數(shù)學家，他在尋找素數(shù)時，采用了一種與眾不同的方法：先將2－N的各數(shù)寫在紙上：

在2的上面畫一個圓圈，然后劃去2的其他倍數(shù)；第一個既未畫圈又沒有被劃去的數(shù)是3，將它畫圈，再劃去3的其他倍數(shù)；現(xiàn)在既未畫圈又沒有被劃去的第一個數(shù) 是5，將它畫圈，并劃去5的其他倍數(shù)……依次類推，一直到所有小于或等于N的各數(shù)都畫了圈或劃去為止。這時，表中畫了圈的以及未劃去的那些數(shù)正好就是小于 N的素數(shù)。

這很像一面篩子，把滿足條件的數(shù)留下來，把不滿足條件的數(shù)篩掉。由于這種方法是厄拉多塞首先發(fā)明的，所以，后人就把這種方法稱作厄拉多塞篩法。
在計算機中，篩法可以用給數(shù)組單元置零的方法來實現(xiàn)。具體來說就是：首先開一個數(shù)組：a[i]，i=1，2，3，…，同時，令所有的數(shù)組元素都等于下標 值，即a[i]=i，當i不是素數(shù)時，令a[i]=0 。當輸出結(jié)果時，只要判斷a[i]是否等于零即可，如果a[i]=0，則令i=i+1，檢查下一個a[i]。
篩法是計算機程序設計中常用的算法之一。

【3】用6N±1法求素數(shù)。
任何一個自然數(shù)，總可以表示成為如下的形式之一：
6N，6N+1，6N+2，6N+3，6N+4，6N+5 (N=0，1，2，…)
顯然，當N≥1時，6N，6N+2，6N+3，6N+4都不是素數(shù)，只有形如6N+1和6N+5的自然數(shù)有可能是素數(shù)。所以，除了2和3之外，所有的素數(shù)都可以表示成6N±1的形式(N為自然數(shù))。
根據(jù)上述分析，我們可以構(gòu)造另一面篩子，只對形如6 N±1的自然數(shù)進行篩選，這樣就可以大大減少篩選的次數(shù)，從而進一步提高程序的運行效率和速度。

在程序上，我們可以用一個二重循環(huán)實現(xiàn)這一點，外循環(huán)i按3的倍數(shù)遞增，內(nèi)循環(huán)j為0－1的循環(huán)，則2(i+j)-1恰好就是形如6N±1的自然數(shù)。