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.

[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;
}
}
```

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 is |
The upper limit is |
The upper limit is |
---|---|---|---|

Implemented in ArrayList(ListImplement.java) | 3,221 ms | Did not come back | - |

Implemented with HashSet(SetImplement.java) | 24 ms | 118 ms | 1,120 ms |

ArrayList |
16 ms | 50 ms | 1,247 ms |

Reference 1 | 31 ms | 276 ms | 7,845 ms |

Reference 2 | 4 ms | 21 ms | 66 ms |

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.

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

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.

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