Java求指定范围内的质数

2014-05-28· 7998 次浏览
## 方法 先把N个自然数按次序排列起来,然后依次划去合数及其倍数。 1不是质数,也不是合数,要划去。 2是质数留下来,然后把2后面的所有能被2整除的数都划去。 2后面第一个没划去的数是3,把3留下,再把3后面所有能被3整除的数都划去。 3后面第一个没划去的数是5,把5留下,再把5后面所有能被5整除的数都划去。 这样一直做下去,就会把不超过N的全部合数都筛掉,留下的就是不超过N的全部质数。 ## 代码 ```java import java.util.Arrays; public class TestPrimeNumber { private static boolean[] FilterNumber(int number) { // 数组标注是否为质数,下标值为质数,那么对应数组元素值为true. 如isPrime[2]=true boolean[] primeFlag = new boolean[number + 1]; // 1不是质数 primeFlag[1] = false; // 将布尔数组元素的值都赋为true Arrays.fill(primeFlag, 2, primeFlag.length, true); // 如果一个数不是质数,那么它应该可以表示成两个非1非自身的数相乘。 // 而这两个数,必然有一个大于平方根一个小于平方根,或者两个都等于平方根。 // 所以只需要遍历到平方根,即可算出所有合数 for (int i = 1; i <= Math.sqrt(number); i++) { if (primeFlag[i]) { // 如果是质数,那么i的倍数不是质数 for (int j = 2 * i; j <= number; j += i) { primeFlag[j] = false; } } } return primeFlag; } public static void getPrimes(int number) { if (number <= 0) { System.out.println("范围必须大于0"); return; } int num = 0; boolean[] primeFlag = FilterNumber(number); System.out.println("范围在" + number + "内的质数有:"); for (int i = 1; i < primeFlag.length; i++) { // 如果数组元素值为false, 则不是质数 if (!primeFlag[i]) continue; // 输出质数 System.out.print(i + " "); // 每输出10个质数换行 if (++num % 10 == 0) System.out.println(); } System.out.println("\n一共有" + num + "个"); } public static void main(String[] args) { getPrimes(100); } } ```