Erdös-Selfridge categorization of primes: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (→{{header|Raku}}: tidy output formatting a bit) |
(Added Java solution) |
||
Line 261: | Line 261: | ||
Category 10: first->1065601 last->15472321 count->28 |
Category 10: first->1065601 last->15472321 count->28 |
||
Category 11: first->8524807 last->8524807 count->1 |
Category 11: first->8524807 last->8524807 count->1 |
||
</pre> |
|||
=={{header|Java}}== |
|||
Uses the PrimeGenerator class from [[Extensible prime generator#Java]]. |
|||
<lang java>import java.util.*; |
|||
public class ErdosSelfridge { |
|||
private int[] primes; |
|||
private int[] category; |
|||
public static void main(String[] args) { |
|||
ErdosSelfridge es = new ErdosSelfridge(1000000); |
|||
System.out.println("First 200 primes:"); |
|||
for (var e : es.getPrimesByCategory(200).entrySet()) { |
|||
int category = e.getKey(); |
|||
List<Integer> primes = e.getValue(); |
|||
System.out.printf("Category %d:\n", category); |
|||
for (int i = 0, n = primes.size(); i != n; ++i) |
|||
System.out.printf("%4d%c", primes.get(i), (i + 1) % 15 == 0 ? '\n' : ' '); |
|||
System.out.printf("\n\n"); |
|||
} |
|||
System.out.println("First 1,000,000 primes:"); |
|||
for (var e : es.getPrimesByCategory(1000000).entrySet()) { |
|||
int category = e.getKey(); |
|||
List<Integer> primes = e.getValue(); |
|||
System.out.printf("Category %2d: first = %7d last = %8d count = %d\n", category, |
|||
primes.get(0), primes.get(primes.size() - 1), primes.size()); |
|||
} |
|||
} |
|||
private ErdosSelfridge(int limit) { |
|||
PrimeGenerator primeGen = new PrimeGenerator(100000, 200000); |
|||
List<Integer> primeList = new ArrayList<>(); |
|||
for (int i = 0; i < limit; ++i) |
|||
primeList.add(primeGen.nextPrime()); |
|||
primes = new int[primeList.size()]; |
|||
for (int i = 0; i < primes.length; ++i) |
|||
primes[i] = primeList.get(i); |
|||
category = new int[primes.length]; |
|||
} |
|||
private Map<Integer, List<Integer>> getPrimesByCategory(int limit) { |
|||
Map<Integer, List<Integer>> result = new TreeMap<>(); |
|||
for (int i = 0; i < limit; ++i) { |
|||
var p = result.computeIfAbsent(getCategory(i), k -> new ArrayList<Integer>()); |
|||
p.add(primes[i]); |
|||
} |
|||
return result; |
|||
} |
|||
private int getCategory(int index) { |
|||
if (category[index] != 0) |
|||
return category[index]; |
|||
int maxCategory = 0; |
|||
int n = primes[index] + 1; |
|||
for (int i = 0; n > 1; ++i) { |
|||
int p = primes[i]; |
|||
if (p * p > n) |
|||
break; |
|||
int count = 0; |
|||
for (; n % p == 0; ++count) |
|||
n /= p; |
|||
if (count != 0) { |
|||
int category = (p <= 3) ? 1 : 1 + getCategory(i); |
|||
maxCategory = Math.max(maxCategory, category); |
|||
} |
|||
} |
|||
if (n > 1) { |
|||
int category = (n <= 3) ? 1 : 1 + getCategory(getIndex(n)); |
|||
maxCategory = Math.max(maxCategory, category); |
|||
} |
|||
category[index] = maxCategory; |
|||
return maxCategory; |
|||
} |
|||
private int getIndex(int prime) { |
|||
return Arrays.binarySearch(primes, prime); |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
First 200 primes: |
|||
Category 1: |
|||
2 3 5 7 11 17 23 31 47 53 71 107 127 191 383 |
|||
431 647 863 971 1151 |
|||
Category 2: |
|||
13 19 29 41 43 59 61 67 79 83 89 97 101 109 131 |
|||
137 139 149 167 179 197 199 211 223 229 239 241 251 263 269 |
|||
271 281 283 293 307 317 349 359 367 373 419 433 439 449 461 |
|||
479 499 503 509 557 563 577 587 593 599 619 641 643 659 709 |
|||
719 743 751 761 769 809 827 839 881 919 929 953 967 991 1019 |
|||
1033 1049 1069 1087 1103 1187 1223 |
|||
Category 3: |
|||
37 103 113 151 157 163 173 181 193 227 233 257 277 311 331 |
|||
337 347 353 379 389 397 401 409 421 457 463 467 487 491 521 |
|||
523 541 547 569 571 601 607 613 631 653 683 701 727 733 773 |
|||
787 797 811 821 829 853 857 859 877 883 911 937 947 983 997 |
|||
1009 1013 1031 1039 1051 1061 1063 1091 1097 1117 1123 1153 1163 1171 1181 |
|||
1193 1217 |
|||
Category 4: |
|||
73 313 443 617 661 673 677 691 739 757 823 887 907 941 977 |
|||
1093 1109 1129 1201 1213 |
|||
Category 5: |
|||
1021 |
|||
First 1,000,000 primes: |
|||
Category 1: first = 2 last = 10616831 count = 46 |
|||
Category 2: first = 13 last = 15482669 count = 10497 |
|||
Category 3: first = 37 last = 15485863 count = 201987 |
|||
Category 4: first = 73 last = 15485849 count = 413891 |
|||
Category 5: first = 1021 last = 15485837 count = 263109 |
|||
Category 6: first = 2917 last = 15485857 count = 87560 |
|||
Category 7: first = 15013 last = 15484631 count = 19389 |
|||
Category 8: first = 49681 last = 15485621 count = 3129 |
|||
Category 9: first = 532801 last = 15472811 count = 363 |
|||
Category 10: first = 1065601 last = 15472321 count = 28 |
|||
Category 11: first = 8524807 last = 8524807 count = 1 |
|||
</pre> |
</pre> |
||