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. .. ..

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.