[Java] Find prime numbers with an Eratosthenes sieve (Part 2)

Introduction

The code of previous post is a high-cost code that "searches the entire list, divides it, and sifts it", as pointed out by @swordone. It turned out. So, based on the hint given by @swordone, I made a major correction to the code.

code

The differences from the previous code are as follows.

• Changed the search list from List <Integer> to boolean [].
• Instead of "list from 2 to upper limit", "list of subscripts from 2 to upper limit" is used.
• First, all the elements of the array are treated as prime numbers (true), and when they are screened out, they are treated as non-prime numbers (false).
• Changed to "Random access to the element of the value to be sieved and sieved" instead of "Exploring the entire list, dividing and sieving".
• By increasing the increment of the for statement by "increment by the value of the current prime number (firstNum)" instead of "increment by 1", only multiples of the current prime number (firstNum) are screened out.

PrimeNumberFinder.java

static void printPrimeNumbers2(int maxNumber) {

	//Step 1: Put "integer from 2 to upper limit" in the search list.
	boolean[] targetNumbers = new boolean[maxNumber + 1];
	Arrays.fill(targetNumbers, true);
	targetNumbers[0] = false;
	targetNumbers[1] = false;

	//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.
	for(int i=2; i<=sqrt; i++) {
		//Step 2: Make the first number in the search list a prime number and screen multiples from the search list.
		//* At this time, the number that has already been sieved (false) is excluded.
		int firstNum = i;
		if (targetNumbers[i]) {
			for (int j=i*firstNum; j<targetNumbers.length; j+=firstNum) {
				targetNumbers[j] = false;
			}
		}
	}

	//Step 4: Move the values remaining in the search list to the prime number list and finish the process.
	for (int i=2; i<targetNumbers.length; i++) {
		if (targetNumbers[i]) {
			primeNumbers.add(i);
		}
	}

	//Display of prime numbers
	System.out.println(primeNumbers.stream().map(pNum -> pNum.toString()).collect(Collectors.joining("\t")));
}

How fast has it been?

• It was more than 10 times faster than the previous code.
• Even if you are not General Gillen, it is a difference that makes you want to say, "Isn't it overwhelming, my army?"

Summary

• Through this code, I was reminded that development that considers "complexity" is important.
• I think there are still some points that can be improved with this code, but ...
• Thank you @swordone for all the hints.