Java USES filter method to find primes up to n example of of Java to find primes
- 2020-04-01 03:17:47
- OfStack
/**
* @author jxqlovedn
* Elatosthenes prime number screening method, please refer to: http://zh.wikipedia.org/zh-cn/ Eratosthenes sieve
*/
public class AratosternyAlgorithm {
public static void getPrimes(int n) {
if(n < 2 || n > 1000000) //The maximum limit of 1 million is due to JVM memory limitations, though there are other flexible ways around this (such as bitmaps)
throw new IllegalArgumentException(" The input parameters n Error! ");
int[] array = new int[n]; //If all the initial Numbers are prime, and some number is prime, the value is 0; For example, if the first number is prime, then array[0] is 0
array[0] = 1; //0 is not a prime number
array[1] = 1; //1 is not a prime number
//The following is the core filtering process
for(int i = 2; i < Math.sqrt(n);i++) { //Let's start with the smallest prime number, 2
if(array[i] == 0) {
for(int j = i*i; j < n; j += i) {
array[j] = 1; //Identifies the position as a non-prime number
}
}
}
//Print all primes up to n, 10 for each row
System.out.println(n + " The primes within are as follows: ");
int count = 0; //The number of primes that have been output
int rowLength = 10; //The number of primes output per line
for(int i = 0; i < array.length; i++) {
if(array[i] == 0) {
if(count % rowLength == 0 && count != 0) {
System.out.println();
}
count++;
System.out.print(i + "t");
}
}
}
public static void main(String[] args) {
getPrimes(99999);
}
}