fork download
copy 
  1. import java.util.ArrayList;
  2. import java.util.Collections;
  3.  
  4. import java.util.PriorityQueue;
  5. import java.util.Comparator;
  6.  
  7. public class Main {
  8. 	public static void main(String[] args) {
  9. 		Sieve sieve = new Sieve();
  10. 		ArrayList<Integer> primes = new ArrayList<Integer>();
  11.  
  12. 		while (primes.size() < 31) {
  13. 			primes.add(sieve.nextPrime());
  14. 		}
  15.  
  16. 		System.out.println("\nPrimes after 31:");
  17. 		System.out.println(primes);
  18.  
  19. 		System.out.println("\nSieve heap after 31:");
  20. 		System.out.println(sieve.queue);
  21.  
  22. 		ArrayList<Sieve.PrimeCounter> sieveState = new ArrayList<Sieve.PrimeCounter>(sieve.queue);
  23. 		Collections.sort(sieveState, sieve.queue.comparator());
  24.  
  25. 		System.out.println("\nOrdered sieve state after 31:");
  26. 		System.out.println(sieveState);
  27.  
  28.  
  29. 		while (primes.size() < 35) {
  30. 			primes.add(sieve.nextPrime());
  31. 		}
  32. 		System.out.println("\nPrimes:");
  33. 		System.out.println(primes);
  34. 	}
  35.  
  36. 	public static class Sieve {
  37. 		public PriorityQueue<PrimeCounter> queue;
  38. 		public Integer current = 2;
  39.  
  40. 		Sieve() {
  41. 			Comparator<PrimeCounter> c = new Comparator<PrimeCounter>() {
  42. 				public int compare(PrimeCounter a, PrimeCounter b) {
  43. 					return a.multiple.compareTo(b.multiple);
  44. 				}
  45. 			};
  46. 			queue = new PriorityQueue<PrimeCounter>(1000, c);
  47. 		}
  48.  
  49. 		public Integer nextPrime() {
  50. 			// Determine the prime
  51.  
  52. 			// If we're not at the first prime.
  53. 			if (!queue.isEmpty()) {
  54. 				PrimeCounter top;
  55. 				// Infinite loop with break.
  56. 				while (true) {
  57. 					top = queue.peek();
  58. 					// The top primecounter needs to be updated.
  59. 					if (top.multiple < current) {
  60. 						top = queue.poll();
  61. 						top.nextMultiple();
  62. 						queue.add(top);
  63. 					}
  64. 					// The current number isn't a prime; go on to the next one.
  65. 					else if (top.multiple == current) {
  66. 						current++;
  67. 					}
  68. 					// We've found a prime.
  69. 					else {
  70. 						break;
  71. 					}
  72. 				}
  73. 			}
  74.  
  75. 			// Handle bookkeeping.
  76. 			Integer prime = current;
  77. 			current++;
  78. 			queue.add(new PrimeCounter(prime));
  79.  
  80. 			// Return the prime.
  81. 			return prime;
  82. 		}
  83.  
  84. 		public static class PrimeCounter {
  85. 			public Integer prime;
  86. 			public Integer multiple;
  87.  
  88. 			PrimeCounter(Integer prime) {
  89. 				this.prime = prime;
  90. 				this.multiple = prime;
  91. 			}
  92.  
  93. 			public void nextMultiple() {
  94. 				multiple += prime;
  95. 			}
  96.  
  97. 			public String toString() {
  98. 				return "[" + prime + ":" + multiple + "]";
  99. 			}
  100. 		}
  101. 	}
  102. }
Success #stdin #stdout 0.03s 245632KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Primes after 31:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127]

Sieve heap after 31:
[[127:127], [11:132], [2:128], [17:136], [67:134], [7:133], [43:129], [29:145], [47:141], [73:146], [23:138], [79:158], [53:159], [19:133], [3:129], [61:183], [37:148], [89:178], [71:142], [41:164], [59:177], [83:166], [31:155], [97:194], [101:202], [103:206], [107:214], [109:218], [113:226], [5:130], [13:130]]

Ordered sieve state after 31:
[[127:127], [2:128], [43:129], [3:129], [5:130], [13:130], [11:132], [7:133], [19:133], [67:134], [17:136], [23:138], [47:141], [71:142], [29:145], [73:146], [37:148], [31:155], [79:158], [53:159], [41:164], [83:166], [59:177], [89:178], [61:183], [97:194], [101:202], [103:206], [107:214], [109:218], [113:226]]

Primes:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 128, 129, 130, 131]
https://ideone.com/E07Te
language:
Java (HotSpot 12)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!