Primes.java
View source code here on GitHub!
- public class Primes
1package euler.lib;
2
3import java.util.Arrays;
4import java.util.ArrayList;
5import java.util.HashMap;
6import java.util.Iterator;
7import java.util.List;
8import java.util.Map;
9import java.util.Optional;
10import java.util.Spliterator;
11import java.util.Spliterators;
12import java.util.function.Consumer;
13import java.util.stream.Stream;
14import java.util.stream.StreamSupport;
15
16public class Primes {
17 private static class Cache {
18 long lastCached;
19 List<Long> primes;
20
21 Cache(long lastCached, List<Long> primes) {
22 this.lastCached = lastCached;
23 this.primes = primes;
24 }
25 }
26
27 private static final Cache CACHE = new Cache(0, new ArrayList<>());
28
29 public static Stream<Long> primes() {
30 return StreamSupport.stream(new PrimeSpliterator(null), false);
31 }
32
33 public static Stream<Long> primesUntil(long limit) {
34 return StreamSupport.stream(new PrimeSpliterator(limit), false);
35 }
36
37 private static class PrimeSpliterator implements Spliterator<Long> {
38 private final PrimeIterator primeIterator;
39
40 PrimeSpliterator(Long limit) {
41 primeIterator = new PrimeIterator(limit);
42 }
43
44 @Override
45 public boolean tryAdvance(Consumer<? super Long> action) {
46 if (primeIterator.hasNext()) {
47 action.accept(primeIterator.next());
48 return true;
49 }
50 return false;
51 }
52
53 @Override
54 public Spliterator<Long> trySplit() {
55 return null; // Sequential iteration only
56 }
57
58 @Override
59 public long estimateSize() {
60 return Long.MAX_VALUE; // Unknown size
61 }
62
63 @Override
64 public int characteristics() {
65 return ORDERED | SIZED | IMMUTABLE | NONNULL;
66 }
67 }
68
69 private static class PrimeIterator implements Iterator<Long> {
70 private final Long limit;
71 private Iterator<Long> primeGenerator;
72 private boolean exhausted = false;
73
74 PrimeIterator(Long limit) {
75 this.limit = limit;
76 primeGenerator = new PrimeGeneratorIterator();
77 }
78
79 @Override
80 public boolean hasNext() {
81 if (exhausted || (limit != null && CACHE.lastCached >= limit)) {
82 return false;
83 }
84 return primeGenerator.hasNext();
85 }
86
87 @Override
88 public Long next() {
89 if (limit != null && CACHE.lastCached >= limit) {
90 exhausted = true;
91 return null;
92 }
93
94 if (primeGenerator.hasNext()) {
95 long prime = primeGenerator.next();
96 if (limit != null && prime >= limit) {
97 exhausted = true;
98 return null;
99 }
100 CACHE.primes.add(prime);
101 CACHE.lastCached = prime;
102 return prime;
103 }
104
105 return null;
106 }
107 }
108
109 private static class PrimeGeneratorIterator implements Iterator<Long> {
110 private final List<Long> initialPrimes = Arrays.asList(2L, 3L, 5L);
111 private final Map<Long, Long> sieve = new HashMap<>();
112 private Iterator<Long> recursivePrimes;
113 private long currentPrime;
114 private long primeSquared;
115 private long step = 2;
116 private long candidate = 2;
117
118 PrimeGeneratorIterator() {
119 initialPrimes.forEach(prime -> {
120 sieve.put(prime, step);
121 step = prime * 2;
122 });
123 recursivePrimes = null;
124 }
125
126 @Override
127 public boolean hasNext() {
128 return true;
129 }
130
131 @Override
132 public Long next() {
133 if (candidate <= 5) {
134 if (candidate == 2) {
135 candidate = 3;
136 return 2L;
137 }
138 if (candidate == 3) {
139 candidate = 5;
140 return 3L;
141 }
142 if (candidate == 5) {
143 candidate = 7;
144 recursivePrimes = new PrimeIterator(null);
145 recursivePrimes.next();
146 currentPrime = recursivePrimes.next();
147 primeSquared = currentPrime * currentPrime;
148 return 5L;
149 }
150 }
151 while (true) {
152 if (sieve.containsKey(candidate)) {
153 step = sieve.remove(candidate);
154 } else if (candidate < primeSquared) {
155 long result = candidate;
156 candidate += 2;
157 return result;
158 } else {
159 step = currentPrime * 2;
160 if (recursivePrimes.hasNext()) {
161 currentPrime = recursivePrimes.next();
162 }
163 primeSquared = currentPrime * currentPrime;
164 }
165 long multiple = candidate;
166 do {
167 multiple += step;
168 } while (sieve.containsKey(multiple));
169 sieve.put(multiple, step);
170 candidate += 2;
171 }
172 }
173 }
174
175 public static Stream<Long> primeFactors(long target) {
176 return StreamSupport.stream(new PrimeFactorSpliterator(target), false);
177 }
178
179 private static class PrimeFactorSpliterator implements Spliterator<Long> {
180 private final PrimeFactorIterator primeFactorIterator;
181
182 PrimeFactorSpliterator(Long limit) {
183 primeFactorIterator = new PrimeFactorIterator(limit);
184 }
185
186 @Override
187 public boolean tryAdvance(Consumer<? super Long> action) {
188 if (primeFactorIterator.hasNext()) {
189 action.accept(primeFactorIterator.next());
190 return true;
191 }
192 return false;
193 }
194
195 @Override
196 public Spliterator<Long> trySplit() {
197 return null; // Sequential iteration only
198 }
199
200 @Override
201 public long estimateSize() {
202 return Long.MAX_VALUE; // Unknown size
203 }
204
205 @Override
206 public int characteristics() {
207 return ORDERED | SIZED | IMMUTABLE | NONNULL;
208 }
209 }
210
211 private static class PrimeFactorIterator implements Iterator<Long> {
212 private Long target;
213 private Long lastPrime;
214 private Iterator<Long> primeGenerator;
215
216 PrimeFactorIterator(Long target) {
217 this.target = target;
218 primeGenerator = new PrimeIterator(null);
219 lastPrime = primeGenerator.next();
220 }
221
222 @Override
223 public boolean hasNext() {
224 return this.target != 1;
225 }
226
227 @Override
228 public Long next() {
229 if (target < 0L) {
230 target = -target;
231 return -1L;
232 }
233 if (target == 0L) {
234 target = 1L;
235 return 0L;
236 }
237 while (hasNext()) {
238 while (target % lastPrime != 0L && lastPrime < target) {
239 lastPrime = primeGenerator.next();
240 }
241 target /= lastPrime;
242 return lastPrime;
243 }
244 return null;
245 }
246 }
247}