正文
【练习总结】题目：筛法遍历素数（Java）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
初学Java，学到流程控制的循环，有个练习题是暴力遍历素数。
因为看过av32186751，知道有个筛法，就想试试。
又受到线性筛法（一）--素数筛法（一） - nerd呱呱 - 博客园中，的这段启发，就有了下面的代码。
引用文字：
我们先定义一个数组来存100000以内数是否的素数，下标表示数，数组的值1表示是素数，0表示不是素数。
我们可以换个角度思考，要找素数，其实只要把不是素数的排除就可以了。
代码：
import java.util.Scanner;
/**
* ShaiFa_Prime__Basic
* @author HmLy.0000
* * * * * * * * * * * * *
*/
public class ShaiFa_Prime__Basic { /**
* 这边，直接用i 来表示"thisNumber[i]" ...
*/
public static void main(String[] args) {
System.out.println();
Scanner scn = new Scanner(System.in);
System.out.println("# 【这是个筛法遍历素数的工具】"); System.out.println("# --> 目前还不能输入同一个数。");
System.out.println("# ");
System.out.println("# ==== -- ==== -- ==== -- ==== ");
System.out.println("# 请指定遍历素数区间范围 : ");
System.out.println("# ---- --- --- ---- --- -- ---- -- -"); boolean[] isPrime_AHA;
int numberArr_i_OP, numberArr_i_ED; while (true) {
System.out.print ("# 指定区间边界<1>, 最少是 2 : | ");
numberArr_i_OP = scn.nextInt();
if (numberArr_i_OP >= 2) {
break;
} else {
System.out.println("# [ERR!!] - === 您输入的值非法，请重新输入！！====");
}//if-else_to_break
}//whileTrue while (true) {
System.out.print ("# 指定区间边界<1>, 最少是 2 : | ");
numberArr_i_ED = scn.nextInt();
if (numberArr_i_ED >= 2) {
break;
} else {
System.out.println("# [ERR!!] - === 您输入的值非法，请重新输入！！====");
}//if-else_to_break
}//whileTrue if (numberArr_i_ED < numberArr_i_OP){
int temp = numberArr_i_ED;
numberArr_i_ED = numberArr_i_OP;
numberArr_i_OP = temp;
}//交换位置 //int largePrim = (numberArr_ED - numberArr_OP + 1);
isPrime_AHA = new boolean[numberArr_i_ED + 1]; for (int i = 0; i <= numberArr_i_ED; i++) {
isPrime_AHA[i] = true;
} isPrime_AHA[0]= false;
isPrime_AHA[1]= false;//先不想办法省掉它俩。。 int nnn_i__tst;
for (int i = 2; i <= numberArr_i_ED; i++) { if(isPrime_AHA[i]){
for (nnn_i__tst = i*2; nnn_i__tst <= numberArr_i_ED; nnn_i__tst++) {
if(nnn_i__tst% i== 0){
isPrime_AHA[nnn_i__tst] = false;
}
}//检查大于2的数是否是其倍数，是，就false。从2 的两倍开始检查 - 因为其前面的必定不是倍数。。。。
}//对所有还没false的进行操作。
}//不光检查2。所有还没false的都得检查。 //打印
System.out.println("# ---- --- --- ---- --- -- ---- -- -");
System.out.println("# 区间为 : |["+ numberArr_i_OP +", "+ numberArr_i_ED +"]");
System.out.println("# 区间长度 : |["+ (numberArr_i_ED +1 - numberArr_i_OP) +"]");
System.out.println("# ---- ---- ---- ---- | ");
int primeCunt = 0;
for (int i = numberArr_i_OP; i <= numberArr_i_ED; i++) {
if (isPrime_AHA[i]) {
primeCunt++;
}
}//数数
System.out.println("# 区间中素数个数 : | "+ primeCunt);
System.out.println("# -- - - ---- --"); for (int i = numberArr_i_OP; i <= numberArr_i_ED; i++) {
if (isPrime_AHA[i]) {
System.out.println("# 区间中的素数 : | "+ i);
}
}//输出
System.out.println("# ---- --- --- ---- --- -- ---- -- -");
}//main
}
/**
* 受到了查到的筛法的启发。
* * * * * * * * * * * * *
* 先前尝试再来个数组，就不用让 i 为 0 和 1
* 的部分被白费，但直接整晕了... 上面这个先简单来，成功了。
*/
为了这个专门预习了数组。
一开始独立写代码，想在开始就不让程序浪费一开始的0和1两个下标，就又弄了一个数组又定义了一堆新变量，然后自己也晕在里面了。。。索性就不管这个，然后就成了。
- - - - - -
对了，一开始的时候弄得那个全是bug的代码似乎还一口气加上了指定遍历开头的功能……
这个的话，是从2开始遍历，只是取值可以设定区间而已，区间只是帮助截取显示的部分，选择小区间并不见得就会减少程序运算量。。。。
- - - - - -
而且，遍历下标倍数的时候上面的代码也弄复杂了。
甭判断这个 % 那个是不是 0 ，直接从 2 到 n 操作一遍 isPrime[i*j] = false ，就成了。。。。
