目錄

一試除法

二埃氏篩

三線性篩(歐拉篩)

---

一試除法

思想：就是判斷某個數x是不是素數,就判斷從2開始到小于=根號x的范圍內有沒有能夠取余不等于0的,這個說明當前值就是x的一個因子，所以不是素數。

代碼：

import java.util.Scanner;public class Javava {public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("求0~300之間的素數：");pan1();//試除法sc.close();}private static void pan1() {int total = 0;for (int i = 2; i <= 300; i++) {int j;for( j = 2; j*j <= i; j++) {if(i%j==0){break;}}if(j*j>i){System.out.println(i+" ");total ++;}}System.out.println("共有"+total+"個");}
}

二埃氏篩

思想：從小到大開始判斷素數,當前x是素數,那么x*x 及以后得x*x+n*x都不在會是素數了，直接排除即可,使用一個boolean型的輔助數組即可

代碼：

import java.util.Scanner;public class Javava {public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("求0~300之間的素數：");pan2();//埃氏篩sc.close();}private static void pan2() {int total = 0;boolean [] arr = new boolean[300];for (int i = 2; i < arr.length; i++) {if(arr[i]==false){for(int j=i*i;j<arr.length;j+=i){arr[j]=true;}}}System.out.println("素數有");for (int i = 2; i < arr.length; i++) {if(arr[i]==false){System.out.print(i+" ");total++;}}System.out.println();System.out.println("共有"+total+"個");}
}

三線性篩(歐拉篩)

思想：因為第二個埃氏篩有重復標記的,也是浪費性能,線性篩是對埃氏篩的進一步優化

代碼：

ArrayList

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;public class Javava {public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("求0~300之間的素數：");pan3();//歐拉篩sc.close();}private static void pan3() {int total = 0;boolean [] arr = new boolean[301];ArrayList<Integer> list = new ArrayList<>();for (int i = 2; i < arr.length; i++) {if(arr[i]==false)list.add(i);for(int j=0;j<list.size()&&i*list.get(j)<=300;j++){arr[i*list.get(j)]=true;if(i%list.get(j)==0){break;}}}System.out.println("素數有");for(int val:list){System.out.print(val+" ");}System.out.println();System.out.println("共有"+list.size()+"個");}
}

二：純粹數組

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;public class Javava {public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("求0~300之間的素數：");pan3();//歐拉篩sc.close();}private static void pan3() {int total = 0;boolean [] arr = new boolean[301];
//        ArrayList<Integer> list = new ArrayList<>();int [] list = new int[301];int idx = 0;for (int i = 2; i < arr.length; i++) {if(arr[i]==false)list[idx++] = i;for(int j=0;j<=idx&&i*list[j]<=300;j++){arr[i*list[j]]=true;if(i%list[j]==0){break;}}}System.out.println("素數有");for(int val:list){System.out.print(val+" ");}System.out.println();System.out.println("共有"+(idx)+"個");}
}