數組和鍊表pk篩選法
耿祥義（2021-1-24）
結構加算法決定效率。這裡我們用數組和鍊表分別實現篩選法（求素數），發現採用數組要遠遠快於鍊表。當然，用鍊表實現時，我們故意採用了不同的算法，這個算法可以有其他的應用，即不完全依賴於數的性質。所以對初學者，理解這裡的兩種算法對於掌握數組和鍊表都是有益的。單擊閱讀原文下載原始碼(提取碼: 2xxy)。
篩選法又稱篩法，具體做法是：先把N個自然數按次序排列起來。1不是素數，也不是合數，要划去（合數是指在大於1的整數，能被1和本身整除外，還能被其他數整除的數）。第二個數2是素數留下來，而把2後面所有能被2整除的數都划去。2後面第一個沒划去的數是3，把3留下，再把3後面所有能被3整除的數都划去。3後面第一個沒划去的數是5，把5留下，再把5後面所有能被5整除的數都划去。這樣一直做下去，就會把不超過N的全部合數都篩掉，留下的就是不超過N的全部素數。
public interface PrimeNumber {
public abstract int[] getPrimeNumber(int n);
首先將2到N之間的自然數存在數組中，然後依據篩選法，將划去的數組元素的值設置為0，最後輸出數組中非零的元素值即可。
import java.util.LinkedList;
public class PrimeNumberByArray implements PrimeNumber {
public int [] getPrimeNumber(int n) {
int a[] = new int [n],i,j;
for(i=2;i<a.length;i++){
a[i]=i;
}
for(i=2;i<a.length;i++){
if(a[i]>0) {
for(j=i+i;j<a.length;j=j+i)
//篩選法，這裡嚴格依賴於數的算數性質
a[j]=0;
}
}
return a;
}
}
（2）使用篩法返回新的鍊表，鍊表長度大於0，進行（1）否則進行（3）。
import java.util.LinkedList;
public class PrimeNumberByLinkedList implements PrimeNumber {
public int [] getPrimeNumber(int n) {
LinkedList<Integer> list = new LinkedList<Integer>();
int a[] = new int[list.size()];
int prime = 0;//存放篩選得到的素數
prime = list.pollFirst();//得到一個素數
list= screeningList(list,prime);
private LinkedList<Integer>
screeningList(LinkedList<Integer> list,int prime){
for(int i=0;i<list.size();i++) {
當n的值比較大時，數組法沒有卡住，鍊表法已經卡住（當然，n再大二者都得卡住）
1 毫秒=1000000 納秒。
public class MainClass {
public static void main(String args[]){
PrimeNumber pn =new PrimeNumberByArray();
long startTime = System.nanoTime();
int a[] =pn.getPrimeNumber(N);
long estimatedTime = System.nanoTime() - startTime;
("數組篩選"+N+"以內素數用時"+estimatedTime+"納秒");
pn = new PrimeNumberByLinkedList();
startTime = System.nanoTime();
int b[] =pn.getPrimeNumber(N);
estimatedTime = System.nanoTime() - startTime;
("鍊表篩選"+N+"以內素數用時"+estimatedTime+"納秒");
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
("\n用鍊表篩選得到的不大於"+N+"素數");
for(int i=0;i<b.length;i++){
System.out.print(b[i]+" ");
推薦閱讀