Java实现埃拉托色尼筛法求素数

Java实现埃拉托色尼筛法求素数

1.显示素数

文章目录

• • 1.显示素数
  • • （1）穷举算法1
    • （2）穷举算法2
    • （3）穷举算法3
    • （4）埃拉托色尼筛选法

（1）穷举算法1

package com.java;//程序清单5-15，求前50个素数，技巧：n的除数不超过n/2；
public class PrimeNumber {public static void main(String[] args) {final int NUMBER_OF_PRIMES = 50;final int NUMBER_OF_PRIMES_PER_LINE = 10;int count = 0;  //计数器int number = 2; //从2开始找素数System.out.println("The first 50 prime numbers are n");while (count < NUMBER_OF_PRIMES) {boolean isPrime = true;for (int divisor = 2; divisor <= number / 2; divisor++) {if (number % divisor == 0) {isPrime = false;break;}}if (isPrime) {count++;if (count % NUMBER_OF_PRIMES_PER_LINE == 0) {System.out.printf("%-5dn", number);} else {System.out.printf("%-5d", number);}}number++;}}
}

（2）穷举算法2

package com.java;//程序清单22-5import java.util.Scanner;public class PrimeNumbers {public static void main(String[] args) {Scanner input = new Scanner(System.in);System.out.print("Find all prime numbers <= n, enter n: ");int n = Int();final int NUMBER_PER_LINE = 10; //每行输出10个数字int count = 0;  //计数器，可控制每行输出int number = 2; //从2开始寻找素数System.out.println("The prime numbers are: ");while (number <= n) {boolean isPrime = true; //假定number是素数for (int divisor = 2; divisor <= (int) (Math.sqrt(number)); divisor++) {if (number % divisor == 0) {isPrime = false;break;}}if (isPrime) {count++;if (count % NUMBER_PER_LINE == 0) {System.out.printf("%7dn", number);} else {System.out.printf("%7d", number);}}number++;   //检查下一个数字是否是素数}System.out.println("n" + count + " prime(s) less than or equal to " + n);}
}

（3）穷举算法3

package com.java;//程序清单22-6，程序清单22-5在for循环的每次迭代都必须计算(int) (Math.sqrt(number))，效率不高
//如果i不是素数，那必须存在一个素数p，满足i=pq且p≤q。因此如果i不是素数，那么可以找出从2到根号i之间的被i整除的素数。
//上述命题的逆否命题为：如果不存在一个素数p，满足i=pq，则i是素数
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class EfficientPrimeNumbers {public static void main(String[] args) {Scanner input = new Scanner(System.in);System.out.print("Find all prime numbers <= n, enter n: ");int n = Int();List<Integer> list = new ArrayList<>();final int NUMBER_PER_LINE = 10;int count = 0;int number = 2;int squareRoot = 1; //检查number是否<=squareRootSystem.out.println("The primes numbers are n");while (number <= n) {boolean isPrime = true;if (squareRoot * squareRoot < number) squareRoot++;for (int k = 0; k < list.size() && (k) <= squareRoot; k++) {if (number % (k) == 0) {isPrime = false;break;}}if (isPrime) {count++;list.add(number);if (count % NUMBER_PER_LINE == 0) {System.out.printf("%-7dn", number);} else {System.out.printf("%-7d", number);}}number++;}System.out.println("n" + count + " prime(s) less than or equal to " + n);}}

（4）埃拉托色尼筛选法

package com.java;//程序清单22-7埃拉托色尼筛选法import java.util.Scanner;public class SieveOfEratosthenes {public static void main(String[] args) {Scanner input = new Scanner(System.in);System.out.println("Find all prime numbers <= n, enter n: ");int n = Int();boolean[] primes = new boolean[n + 1];for (int i = 0; i < primes.length; i++) {primes[i] = true;}//判断从2到根号n中的数是否为素数for (int k = 2; k <= n / k; k++) {  //其中k为被判断的数字if (primes[k]) {	//为素数，则将其倍数置为非素数for (int i = k; i <= n / k; i++) {  //其中i为倍数primes[k * i] = false;}}}final int NUMBER_PER_LINE = 10;int count = 0;for (int i = 2; i < primes.length; i++) {if (primes[i]) {count++;if (count % NUMBER_PER_LINE == 0) {System.out.printf("%7dn", i);} else {System.out.printf("%7d", i);}}}System.out.println("n" + count + " prime(s) less than or equal to " + n);}
}