source code clone download copy to clipboard report bug / make suggestion

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

clone download copy to clipboard

• upload with new input
  You have reached a limit of free submissions this month.
  You cannot send submissions this month anymore because of exceeding your monthly limit. Please recharge your account.
  
• # 1:   hide show   clone   input   413 days 16 hours ago    Success

  result: Success     time: 0.03s    memory: 245632 kB     returned value: 0

  input: no
  output:

  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]