public class PrimeNumber { public static void main(String[] args) { boolean b = true; //遍历100以内的天然数 for (int i = 2; i <= 100; i++) { //j：被i除 for (int j = 2; j < i; j++) { if (i % j == 0) { //%是求模运算，即2%10=2，10%2=0，10%3=1。 b = false; } } if (b) { System.out.print(i + " "); } b = true; } }}输出结果：
public class PrimeNumber { public static void main(String[] args) { //获取当前时间隔断1970-01-01 00:00:00的毫秒数 long start = System.currentTimeMillis(); boolean b = true; //遍历100以内的天然数 for (int i = 2; i <= 100000; i++) { //j：被i去除 for (int j = 2; j < i; j++) { if (i % j == 0) { //%是求模运算，即2%10=2，10%2=0，10%3=1。 b = false; } } if (b) { System.out.print(i + " "); } b = true; } //获取当前时间隔断1970-01-01 00:00:00的毫秒数 long end = System.currentTimeMillis(); System.out.println("\n泯灭时间：" + (end - start)); //6243毫秒 }}运行结果：
public class PrimeNumber { public static void main(String[] args) { //获取当前时间隔断1970-01-01 00:00:00的毫秒数 long start = System.currentTimeMillis(); //遍历100以内的天然数 for (int i = 2;i<=100000;i++){ boolean b = true; for (int j=2;j<i;j++){ if (i % j == 0){ //%是求模运算，即2%10=2，10%2=0，10%3=1。 b = false; break;//优化一：只对本身非质数的天然数是有用的 } } if (b){ System.out.print(i+" "); } } long end = System.currentTimeMillis(); System.out.println("\n泯灭时间："+(end-start)); //优化一后：泯灭时间 619ms }}这一次，我在最内层的if语句中参加了 break;
public class PrimeNumber { public static void main(String[] args) { //获取当前时间隔断1970-01-01 00:00:00的毫秒数 long start = System.currentTimeMillis(); //遍历100以内的天然数 for (int i = 2;i<=100000;i++){ boolean b = true; //优化二：对本身是质数的天然数是有用的 for (int j=2;j<Math.sqrt(i);j++){ if (i % j == 0){ //%是求模运算，即2%10=2，10%2=0，10%3=1。 b = false; } } if (b){ System.out.print(i+" "); } } long end = System.currentTimeMillis(); System.out.println("\n泯灭时间："+(end-start)); //优化二：122ms }}运行结果：
可以看到，如今运行结果相比优化一又快了，用了122ms。
方法四：
最终优化：把优化一和优化二联合。
public class PrimeNumber { public static void main(String[] args) { //获取当前时间隔断1970-01-01 00:00:00的毫秒数 long start = System.currentTimeMillis(); //遍历100以内的天然数 for (int i = 2;i<=100000;i++){ boolean b = true; //优化二：对本身是质数的天然数是有用的 for (int j=2;j<Math.sqrt(i);j++){ if (i % j == 0){ //%是求模运算，即2%10=2，10%2=0，10%3=1。 b = false; break;//优化一：只对本身非质数的天然数是有用的 } } if (b){ System.out.print(i+" "); } } long end = System.currentTimeMillis(); System.out.println("\n泯灭时间："+(end-start)); //优化一加优化二：33ms }}运行结果：
两种算法优化联合在一起结果不问可知，输出10万以内的质数仅用了33毫秒
试除法
int N = 29; //任意选择一个 N，以29为例int flag = 1; //flag记录 N 的属性。1 代表 N 是质数， 0 则代表不是。我们先默认它是for(int i = 2;i < N;i++){ if(N % i == 0){ //当 N 除以 i 的余数为 0，阐明 N 被 i 整除，即 N 为合数 flag = 0; break; //由于 N 已经被证实是合数，不必要再继续运算了，跳出循环 }}//算法竣事，最终 flag 为 1 体现质数，flag 为 0 体现合数。
int N = 29; int flag = 1; if(N % 2 == 0) flag = 0; //起首测试 N 是否是偶数else for(int i = 3;i * i < N;i += 2){ //与刚才差异的是，我们先从 3 开始，每次增长 2，一直 //到根号下 N 为止。如许我们的测试就在奇数中睁开 if(N % i == 0){ flag = 0; break; }}//算法竣事，最终 flag 为 1 体现质数，flag 为 0 体现合数。
