Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>There are a few issues here. First, lets talk about the algorithm. Your <code>isPrime</code> method is actually the very thing that the sieve is designed to avoid. When you get to a number in the sieve, <em>you already know it's prime</em>, you don't need to test it. If it weren't prime, it would already have been eliminated as a factor of a lower number. </p> <p>So, point 1:</p> <ul> <li>You can eliminate the <code>isPrime</code> method altogether. It should never return false.</li> </ul> <p>Then, there are implementation issues. <code>primes.contains</code> and <code>primes.remove</code> are problems. They run in linear time on an <code>ArrayList</code>, because they require checking each element or rewriting a large portion of the backing array.</p> <p>Point 2:</p> <ul> <li>Either mark values in place (use <code>boolean[]</code>, or use some other more appropriate data structure.)</li> </ul> <p>I typically use something like <code>boolean primes = new boolean[upper+1]</code>, and define <code>n</code> to be included if <code>!(primes[n])</code>. (I just ignore elements 0 and 1 so I don't have to subtract indices.) To "remove" an element, I set it to true. You could also use something like <code>TreeSet&lt;Integer&gt;</code>, I suppose. Using <code>boolean[]</code>, the method is near-instantaneous. </p> <p>Point 3:</p> <ul> <li><code>sum</code> needs to be a long. The answer (roughly 1.429e11) is larger than the maximum value of an integer (2^31-1)</li> </ul> <p>I can post working code if you like, but here's a test output, without spoilers:</p> <pre><code>public static void main(String[] args) { long value; long start; long finish; start = System.nanoTime(); value = arrayMethod(2000000); finish = System.nanoTime(); System.out.printf("Value: %.3e, time: %4d ms\n", (double)value, (finish-start)/1000000); start = System.nanoTime(); value = treeMethod(2000000); finish = System.nanoTime(); System.out.printf("Value: %.3e, time: %4d ms\n", (double)value, (finish-start)/1000000); } </code></pre> <p>output:</p> <pre><code>Using boolean[] Value: 1.429e+11, time: 17 ms Using TreeSet&lt;Integer&gt; Value: 1.429e+11, time: 4869 ms </code></pre> <p><strong>Edit:</strong> Since spoilers are posted, here's my code:</p> <pre><code>public static long arrayMethod(int upper) { boolean[] primes = new boolean[upper+1]; long sum = 0; for (int i = 2; i &lt;=upper; i++) { if (!primes[i]) { sum += i; for (int k = 2*i; k &lt;= upper; k+=i) { primes[k] = true; } } } return sum; } public static long treeMethod(int upper) { TreeSet&lt;Integer&gt; primes = new TreeSet&lt;Integer&gt;(); for (int i = 2; i &lt;= upper; i++) { primes.add(i); } long sum = 0; for (Integer i = 2; i != null; i=primes.higher(i)) { sum += i; for (int k = 2*i; k &lt;= upper; k+=i) { primes.remove(k); } } return sum; } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POSum of all prime numbers below 2 million
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USmaybeWeCouldStealAVan
    1. USmaybeWeCouldStealAVan
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COHe needs the `isPrime` method. Just do not apply them to the members of the `prime` list, but to the new others, the successive integers of the main loop (`i`). And for it, a list is more efficient (just iterate it to find if any of the primes is a divisor of the `i` being checked).
      singulars
      1. PO
      1. USSJuan76
    2. CO@SJuan76 Nope, he doesn't. Try his code as is (though, with a smaller value for upper), then replace the code in `isPrime` with `return true;`. Your answer will not change.
      singulars
      1. PO
      1. USmaybeWeCouldStealAVan
    3. COyou should never `remove` anything, in a sieve. Your timings prove it. So, no place for `either` in your 2nd point. :) Nevertheless, your answer is the most to-the-point, IMO.
      singulars
      1. PO
      1. USWill Ness
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload