[GO] [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.

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?

The upper limit is10^2 The upper limit is10^3 The upper limit is10^4 The upper limit is10^5
Last code 54ms 55ms 61ms 102ms
This code 0ms 1ms 1ms 9ms

Summary

Recommended Posts

[Java] Find prime numbers with an Eratosthenes sieve (Part 2)
[Java] Find prime numbers with an Eratosthenes sieve
How to find Java prime numbers
Calculate prime numbers in Java
Create an immutable class with JAVA
Java to learn with ramen [Part 1]
Server processing with Java (Introduction part.1)
Run an application made with Java8 with Java6
[Java] Create an executable module with Gradle
Getting Started with Java Starting from 0 Part 1
AWS Lambda with Java starting now Part 1
Until you insert an S3 object into an EC2 DB with Lambda @ java: Java [Part 2]
Until you insert an S3 object into an EC2 DB with Lambda @ java: Java [Part 1]
Quick learning Java "Introduction?" Part 1 Building an environment
JSON with Java and Jackson Part 2 XSS measures
Build an E2E test environment with Selenium (Java)
[Algorithm] N numbers with an interval of X