The article is written in Go
 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
package main
 
import "log"
 
func main() {
    // max uint32 is not prime
    c := uint32(1<<32 - 1)
    // a few primes near the top of the range.  source: prime pages.
    for _, p := range []uint32{1<<32 - 5, 1<<32 - 17, 1<<32 - 65, 1<<32 - 99} {
        for ; c > p; c-- {
            if prime(c) {
                log.Fatalf("prime(%d) returned true", c)
            }
        }
        if !prime(p) {
            log.Fatalf("prime(%d) returned false", p)
        }
        c--
    }
}
 
func prime(n uint32) bool {
    // bases of 2, 7, 61 are sufficient to cover 2^32
    switch n {
    case 0, 1:
        return false
    case 2, 7, 61:
        return true
    }
    // compute s, d where 2^s * d = n-1
    nm1 := n - 1
    d := nm1
    s := 0
    for d&1 == 0 {
        d >>= 1
        s++
    }
    n64 := uint64(n)
    for _, a := range []uint32{2, 7, 61} {
        // compute x := a^d % n
        x := uint64(1)
        p := uint64(a)
        for dr := d; dr > 0; dr >>= 1 {
            if dr&1 != 0 {
                x = x * p % n64
            }
            p = p * p % n64
        }
        if x == 1 || uint32(x) == nm1 {
            continue
        }
        for r := 1; ; r++ {
            if r >= s {
                return false
            }
            x = x * x % n64
            if x == 1 {
                return false
            }
            if uint32(x) == nm1 {
                break
            }
        }
    }
    return true
}