StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Here is simple pseudocode, as requested:</p> <pre><code>function isStrongPseudoprime(n, a) d := n - 1; s := 0 while d % 2 == 0 d := d / 2 s := s + 1 t := powerMod(a, d, n) if t == 1 return ProbablyPrime while s > 0 if t == n - 1 return ProbablyPrime t := (t * t) % n s := s - 1 return Composite function isPrime(n) for i from 1 to k a := randInt(2, n-1) if isStrongPseudoprime(n, a) == Composite return Composite return ProbablyPrime function powerMod(b, e, m) x := 1 while e > 0 if e % 2 == 1 x := (b * x) % m b := (b * b) % m e := e // 2 # integer division return x </code></pre> <p>The <code>isStrongPseudoprime</code> function tests if <em>a</em> is a witness to the compositeness of <em>n</em>; note that if <code>isStrongPseudoprime</code> returns <code>Composite</code> the number is definitely composite, but the opposite of that is <code>ProbablyPrime</code> because there is a chance that the number is still composite. The <code>isPrime</code> function tests <em>k</em> witnesses; by setting the value of <em>k</em> you can determine the likelihood of error as 1 chance in 4^<em>k</em>. Most people use a value of <em>k</em> somewhere between 10 and 25. The <code>powerMod</code> function performs exponentiation by squaring, and is provided on the chance that your language doesn't provide it for you.</p> <p>If you want to know more about the mathematics behind this test, I modestly recommend this <a href="http://programmingpraxis.com/essays" rel="nofollow">essay</a> at my blog, which also includes implementations in five languages, though none of them is VBA.</p> <p>EDIT: Although he didn't say so, what the original poster actually wants to do is to find the sum of the primes less than two million and thus solve Project Euler 10. Looping through the numbers from 2 to <em>n</em> is a very inefficient way to sum the primes less than <em>n</em>; instead, the recommended method is to use a sieve. Pseudocode again:</p> <pre><code>function sumPrimes(n) sum := 0 sieve := makeArray(2..n, True) for p from 2 to n step 1 if sieve[p] sum := sum + p for i from p * p to n step p sieve[i] := False return sum </code></pre> <p>The algorithm used here is the Sieve of Eratosthenes, invented over two thousand years ago by a Greek mathematician. Again, an explanation and code is in the <a href="http://programmingpraxis.com/essays" rel="nofollow">essay</a> at my blog.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

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