Here is simple pseudocode, as requested:
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
The isStrongPseudoprime
function tests if a is a witness to the compositeness of n; note that if isStrongPseudoprime
returns Composite
the number is definitely composite, but the opposite of that is ProbablyPrime
because there is a chance that the number is still composite. The isPrime
function tests k witnesses; by setting the value of k you can determine the likelihood of error as 1 chance in 4^k. Most people use a value of k somewhere between 10 and 25. The powerMod
function performs exponentiation by squaring, and is provided on the chance that your language doesn't provide it for you.
If you want to know more about the mathematics behind this test, I modestly recommend this essay at my blog, which also includes implementations in five languages, though none of them is VBA.
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 n is a very inefficient way to sum the primes less than n; instead, the recommended method is to use a sieve. Pseudocode again:
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
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 essay at my blog.