Try implementing the Eratosthenes sieve using the Java standard library

Introduction

I usually develop packaged software, but recently I started a competition pro. It was completely different from the usual way of writing code, so I was very confused (I solved the problem thinking that I would not be killed if I wrote such code), and I was wondering what would happen if I implemented this as usual.

In such a case, @ nkojima's [Java] Eratosthenes sieve for prime numbers and [Java] Eratosthenes sieve for prime numbers (Part 2)) , I thought it would be a good subject, so I tried to improve the readability using the standard library.

At this time, I will try to use the collection properly.

code

[Java] Finding prime numbers with an Eratosthenes sieve (Part 2), refer to ʻArrayList, HashSet, ʻArrayList <Boolean. I changed it to> and implemented it.

ListImplement.java


package practise.algorithm.eratosthenes.qiita;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class ListImplement {
	private static final int MIN_PRIME_NUMBER = 2;

	public static void main(String[] args) {
		new ListImplement().execute();
	}

	private void execute() {
		Scanner sc = new Scanner(System.in);
		int maxNumber = sc.nextInt();

		List<Integer> primeNumbers = enumeratePrimeNumbers(maxNumber);

		System.out.println(primeNumbers.toString());
	}

	private List<Integer> enumeratePrimeNumbers(int maxNumber) {
		List<Integer> targets = createSearchTargets(maxNumber);

		sieve(targets, maxNumber);

		return targets;
	}

	//Create a search list from 2 to maxNumber
	private List<Integer> createSearchTargets(int maxNumber) {
		List<Integer> targets = new ArrayList<>(maxNumber);
		for(int i = MIN_PRIME_NUMBER; i <= maxNumber; i++) {
			targets.add(i);
		}
		return targets;
	}

	//Sift multiples of the start value of the search list from the search list
	//Do the above until the start value of the search list reaches the square root of maxNumber.
	private void sieve(List<Integer> targets, int maxNumber) {
		int sqrt = (int)  Math.sqrt(maxNumber);
		for(int i = MIN_PRIME_NUMBER; i <= sqrt; i++) {
			int firstNum = i;
			if(targets.contains(firstNum)) {//★★★ Part to judge whether it is a sieve eye ★★★
				//Since the square of the first value has already been sieved
				for(int j = firstNum * firstNum; j <= maxNumber; j += firstNum) {
					targets.remove(Integer.valueOf(j));//★★★ Sieve part ★★★
				}
			}
		}
	}

}

SetImplement.java


package practise.algorithm.eratosthenes.qiita;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class SetImplement {
	private static final int MIN_PRIME_NUMBER = 2;

	public static void main(String[] args) {
		new SetImplement().execute();
	}

	private void execute() {
		Scanner sc = new Scanner(System.in);
		int maxNumber = sc.nextInt();

		Set<Integer> primeNumbers = enumeratePrimeNumbers(maxNumber);

		System.out.println(primeNumbers.toString());
	}

	private Set<Integer> enumeratePrimeNumbers(int maxNumber) {
		Set<Integer> targets = createSearchTargets(maxNumber);

		sieve(targets, maxNumber);

		return targets;
	}

	//Make a numerical list from 2 to maxNumber
	private Set<Integer> createSearchTargets(int maxNumber) {
		Set<Integer> targets = new HashSet<>(maxNumber);
		for(int i = MIN_PRIME_NUMBER; i <= maxNumber; i++) {
			targets.add(i);
		}
		return targets;
	}

	//Sift multiples of the start value of the search list from the search list
	//Do the above until the start value of the search list reaches the square root of maxNumber.
	private void sieve(Set<Integer> targets, int maxNumber) {
		int sqrt = (int)  Math.sqrt(maxNumber);
		for(int i = MIN_PRIME_NUMBER; i <= sqrt; i++) {
			int firstNum = i;
			if(targets.contains(firstNum)) {//★★★ Part to judge whether it is a sieve eye ★★★
				//Since the square of the first value has already been sieved
				for(int j = firstNum * firstNum; j <= maxNumber; j += firstNum) {
					targets.remove(j);//★★★ Sieve part ★★★
				}
			}
		}
	}
}

BooleanArrayListImplement.java


package practise.algorithm.eratosthenes.qiita;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class BooleanArrayListImplement {
	private static final int MIN_PRIME_NUMBER = 2;

	public static void main(String[] args) {
		new BooleanArrayListImplement().execute();
	}

	private void execute() {
		Scanner sc = new Scanner(System.in);
		int maxNumber = sc.nextInt();

		List<Integer> primeNumbers = enumeratePrimeNumbers(maxNumber);

		System.out.println(primeNumbers.toString());
	}

	private List<Integer> enumeratePrimeNumbers(int maxNumber) {
		List<Boolean> targets = createSearchTargets(maxNumber);

		List<Integer> primeNumbers = extracePrimeNumbers(targets);

		return primeNumbers;
	}

	//Create a Boolean search list from 0 to maxNumber
	//Start from 0 to set index as the number of search targets
	//Determine if it is a prime number by boolean
	private List<Boolean> createSearchTargets(int maxNumber) {
		List<Boolean> targets = new ArrayList<>(maxNumber + 1);
		targets.add(false);//Because 0 is not a prime number
		targets.add(false);//Because 1 is not a prime number
		for(int i = MIN_PRIME_NUMBER; i <= maxNumber; i++) {
			targets.add(true);
		}
		return targets;
	}

	//Sift multiples of the start value of the search list from the search list
	//Do the above until the start value of the search list reaches the square root of maxNumber.
	private List<Integer> extracePrimeNumbers(List<Boolean> targets) {
		int maxNumber = targets.size() - 1;

		sieve(targets, maxNumber);

		List<Integer> primeNumbers = convertToNumList(targets);

		return primeNumbers;
	}

	private void sieve(List<Boolean> targets, int maxNumber) {
		int sqrt = (int)  Math.sqrt(maxNumber);
		for(int i = MIN_PRIME_NUMBER; i <= sqrt; i++) {
			int firstNum = i;
			if(targets.get(i)) {//★★★ Part to judge whether it is a sieve eye ★★★
				//Since the square of the first value has already been sieved
				for(int j = firstNum * firstNum; j <= maxNumber; j += firstNum) {
					targets.set(j, false);//★★★ Sieve part ★★★
				}
			}
		}
	}

	private List<Integer> convertToNumList(List<Boolean> targets) {
		List<Integer> numbers = new ArrayList<>();
		for(int i = 0; i < targets.size(); i++) {
			if(targets.get(i)) {
				numbers.add(i);
			}
		}
		return numbers;
	}
}

Speed summary

It is a summary of execution time (average of 5 executions). ʻArrayList is the fastest, and ʻArrayList is out of the question. None of them can be implemented using arrays. .. ..

Implementation The upper limit is10^5 The upper limit is10^6 The upper limit is10^7
Implemented in ArrayList(ListImplement.java) 3,221 ms Did not come back -
Implemented with HashSet(SetImplement.java) 24 ms 118 ms 1,120 ms
ArrayListImplemented in(BooleanArrayListImplement.java) 16 ms 50 ms 1,247 ms
Reference 1 31 ms 276 ms 7,845 ms
Reference 2 4 ms 21 ms 66 ms

Cause of the difference in speed

I wrote a ★ mark in the code, but I think the following two points are the major factors.

--The part that determines whether it is a sieve --Sieving part

The elements are accessed in each place, and the access method at this time is as follows.

--Implementation of ʻArrayList: Search from the front of the array → Linear search --Implementation of HashSet: Access the target object with a hash table → Random access via hash table --Implementation of ʻArrayList <Boolean> : Access array by index → Random access

After all, the complexity order is ʻArrayList is $ O (n ^ 2 loglogn) $, HashSet and ʻArrayList <Boolean> are $ O (nloglogn) $ (Looking at the execution results, it seems that this is not the case with this implementation. .) I think it is. (The loglogn part was googled. [This article](https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0#%E4%BE%8B-14-%E3%82%A8%E3%83%A9 % E3% 83% 88% E3% 82% B9% E3% 83% 86% E3% 83% 8D% E3% 82% B9% E3% 81% AE% E3% 81% B5% E3% 82% 8B% E3 There is also% 81% 84-on-loglogn).)

Arrays are faster than ʻArrayList and ʻArrayList <Boolean> than HashSet because there is no hash value calculation when accessing the element, and there is no array extension operation. Probably because there are no other extra operations.

Summary

When I actually tried it, I felt as follows.

--When using it in practice, it will be a little slower, but readability will be important, so implement Set. --When speed is important, write a comment and implement the array. --ʻArrayList `If you use it, make it an array (comments are required anyway)

It's interesting to see a lot of algorithms that I haven't seen before when I play a competition pro. It is around this time that I want to make good use of my business.

Finally

――When selecting a collection data structure, I implemented it as if it were a Set to eliminate duplicates and a List if there were duplicates. I just didn't want it to affect speed so much that it happened to be a problem, so I'm glad I noticed it now. ――Thanks to @nkojima for making a wonderful post, I was able to study hard. Thank you. ――I think there are many places where you haven't studied enough, but if there are any strange things, I would like you to gently throw Masakari.

Recommended Posts

Try implementing the Eratosthenes sieve using the Java standard library
Try global hooking in Java using the JNativeHook library
Try adding text to an image in Scala using the Java standard library
[Java] Try editing the elements of the Json string using the library
Try using the Stream API in Java
[Java] Use cryptography in the standard library
Try using the Wii remote with Java
Try accessing the dataset from Java using JZOS
Try using the COTOHA API parsing in Java
Output the maximum value from the array using Java standard output
Try using RocksDB in Java
Try scraping using java [Notes]
I tried using the CameraX library with Android Java Fragment
Create a simple web server with the Java standard library com.sun.net.httpserver
Try implementing Android Hilt in Java
[Java] Try to solve the Fizz Buzz problem using recursive processing
Java comparison using the compareTo () method
Try using Redis with Java (jar)
Welcome to the Java Library Swamp! !!
[Java] Try to implement using generics
Try using the messaging system Pulsar
Try using IBM Java method tracing
Try using Hyperledger Iroha's Java SDK
[Java] Where did you try using java?
Parse and objectize JSON using the @JsonProperty annotation of the Java library Jackson
Display Japanese calendar and days of the week using java8 standard class
Java: Try implementing your own comma-separated formatter
Try using Java framework Nablarch [Web application]
Try using || instead of the ternary operator
Newcomer training using the Web-Basic programming using Java-
Try using the Rails API (zip code)
Study Java Try using Scanner or Map
Try using JSON format API in Java
Try calling the CORBA service in Java 11+
Try using JobScheduler's REST-API --Java RestClient implementation--
[Java] Color the standard output to the terminal
Try using the Emotion API from Android
Try implementing GraphQL server using grahpql-java-tools (+ kotlin)
Try using JobScheduler's REST-API --Java RestClient Test class-
ChatWork4j for using the ChatWork API in Java
Newcomer training using the Web-Basic programming / classes using Java-
Try calling the CORBA service from Spring (Java)
Try using Sourcetrail (win version) in Java code
Try using GCP's Cloud Vision API in Java
Try using Sourcetrail (macOS version) in Java code
Try similar search of Image Search using Java SDK [Search]
Try the free version of Progate [Java II]
Create a multi-key map with the standard library
Display "Hello World" in the browser using Java
Display "Hello World" in the browser using Java
[Java] Find prime numbers with an Eratosthenes sieve
Use Java external library for the time being
Try communication using gRPC on Android + Java server
Does not recognize the library when implementing jcaptcha
[Java] Try to solve the Fizz Buzz problem
Try the free version of Progate [Java I]