[GO] [Java] Find prime numbers with an Eratosthenes sieve

Introduction

In my usual development, I don't have a chance to touch the textbook algorithm, so I wrote a code to find a prime number using "Eratosthenes Sieve" as a brain teaser.

code

PrimeNumberFinder.java


static void printPrimeNumbers(int maxNumber) {

	//Step 1: Put "integer from 2 to upper limit" in the search list.
	List<Integer> targetNumbers = IntStream.rangeClosed(2, maxNumber).boxed().collect(Collectors.toList());

	//Prime number list
	List<Integer> primeNumbers = new ArrayList<Integer>();

	int sqrt = (int) Math.sqrt(maxNumber);

	//Step 3: Continue the sieving operation until the first value in the search list reaches the square root of the argument.
	while(targetNumbers.get(0)<=sqrt) {
		//Step 2: Put the first number in the search list into the prime number list and screen multiples from the search list.
		int firstNum = targetNumbers.get(0);
		primeNumbers.add(firstNum);
		targetNumbers.removeIf(num -> (num % firstNum == 0));
	}

	//Step 4: Move the values remaining in the search list to the prime number list and finish the process.
	primeNumbers.addAll(targetNumbers);

	//Display of prime numbers
	System.out.println(primeNumbers.stream().map(pNum -> pNum.toString()).collect(Collectors.joining("\t")));
}
//Output result when 100 is specified in the argument of printPrimeNumbers
2	3	5	7	11	13	17	19	23	29	31	37	41	43	47	53	59	61	67	71	73	79	83	89	97	

Digression

Recommended Posts

[Java] Find prime numbers with an Eratosthenes sieve
[Java] Find prime numbers with an Eratosthenes sieve (Part 2)
How to find Java prime numbers
Calculate prime numbers in Java
Create an immutable class with JAVA
Run an application made with Java8 with Java6
[Java] Create an executable module with Gradle
[Algorithm] N numbers with an interval of X
Judge prime numbers
Try implementing the Eratosthenes sieve using the Java standard library
Quickly implement a singleton with an enum in Java