<!-- canonical: https://efficientnewlanguage.org/eml-p/projects/P068-prime-explorer/ | updated: 2026-10-14 -->

# P068 Prime explorer

The primes up to 100,000 by the sieve of Eratosthenes, any number up to a trillion broken into prime factors, twin primes, every way an even number is a sum of two primes, and the gaps between primes with how often each occurs.

EML-P project `projects/prime-explorer` in the EML language repo: 2 module(s), entry `main.eml`, terminal UI. There, `eml project run projects/prime-explorer` runs it and `eml project verify projects/prime-explorer` replays every session under CPython (two hash seeds) and in the interpreter; the site build replays every session in the interpreter again and publishes a session only if its screen matches.

Built on verified corpus cases: sieve-of-eratosthenes (https://efficientnewlanguage.org/cases/094-sieve-of-eratosthenes/), prime-factorization (https://efficientnewlanguage.org/cases/060-prime-factorization/).

## Sessions

### bad-input - interpreter: byte-equal to the golden

Input:

```text
0
x
1
1
100001
abc

2
1
1000000000000

4
7
2

5
9

6
```

Screen:

```text
== Prime explorer ==
Primes by the sieve of Eratosthenes, prime factors, twins, Goldbach sums and gaps.

1) primes up to  2) prime factors  3) twin primes  4) Goldbach  5) gaps  6) quit
choice> 0
Pick a number from 1 to 6.

1) primes up to  2) prime factors  3) twin primes  4) Goldbach  5) gaps  6) quit
choice> x
Pick a number from 1 to 6.

1) primes up to  2) prime factors  3) twin primes  4) Goldbach  5) gaps  6) quit
choice> 1
limit (2 to 100000)> 1
Type a whole number from 2 to 100000.
limit (2 to 100000)> 100001
Type a whole number from 2 to 100000.
limit (2 to 100000)> abc
Type a whole number from 2 to 100000.
limit (2 to 100000)> 
Cancelled.

1) primes up to  2) prime factors  3) twin primes  4) Goldbach  5) gaps  6) quit
choice> 2
number (2 to 999999999999)> 1
Type a whole number from 2 to 999999999999.
number (2 to 999999999999)> 1000000000000
Type a whole number from 2 to 999999999999.
number (2 to 999999999999)> 
Cancelled.

1) primes up to  2) prime factors  3) twin primes  4) Goldbach  5) gaps  6) quit
choice> 4
even number (4 to 100000)> 7
Goldbach's question is about even numbers.
even number (4 to 100000)> 2
Type a whole number from 4 to 100000.
even number (4 to 100000)> 
Cancelled.

1) primes up to  2) prime factors  3) twin primes  4) Goldbach  5) gaps  6) quit
choice> 5
limit (10 to 100000)> 9
Type a whole number from 10 to 100000.
limit (10 to 100000)> 
Cancelled.

1) primes up to  2) prime factors  3) twin primes  4) Goldbach  5) gaps  6) quit
choice> 6
Bye.
```

### basic - interpreter: byte-equal to the golden

Input:

```text
1
100
1
10000
2
600851475143
2
1000003
2
360
3
1000
4
100
5
1000
6
```

Screen:

```text
== Prime explorer ==
Primes by the sieve of Eratosthenes, prime factors, twins, Goldbach sums and gaps.

1) primes up to  2) prime factors  3) twin primes  4) Goldbach  5) gaps  6) quit
choice> 1
limit (2 to 100000)> 100
25 primes up to 100: 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

1) primes up to  2) prime factors  3) twin primes  4) Goldbach  5) gaps  6) quit
choice> 1
limit (2 to 100000)> 10000
1229 primes up to 10000: 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 131 137 139 149 151 157 163 167 173 ... and 1189 more

1) primes up to  2) prime factors  3) twin primes  4) Goldbach  5) gaps  6) quit
choice> 2
number (2 to 999999999999)> 600851475143
600851475143 = 71 x 839 x 1471 x 6857

1) primes up to  2) prime factors  3) twin primes  4) Goldbach  5) gaps  6) quit
choice> 2
number (2 to 999999999999)> 1000003
1000003 is prime.

1) primes up to  2) prime factors  3) twin primes  4) Goldbach  5) gaps  6) quit
choice> 2
number (2 to 999999999999)> 360
360 = 2^3 x 3^2 x 5

1) primes up to  2) prime factors  3) twin primes  4) Goldbach  5) gaps  6) quit
choice> 3
limit (5 to 100000)> 1000
35 twin prime pairs up to 1000: 3-5 5-7 11-13 17-19 29-31 41-43 59-61 71-73 101-103 107-109 137-139 149-151 179-181 191-193 197-199 227-229 239-241 269-271 281-283 311-313 ... and 15 more

1) primes up to  2) prime factors  3) twin primes  4) Goldbach  5) gaps  6) quit
choice> 4
even number (4 to 100000)> 100
100 is a sum of two primes in 6 ways: 3+97 11+89 17+83 29+71 41+59 47+53

1) primes up to  2) prime factors  3) twin primes  4) Goldbach  5) gaps  6) quit
choice> 5
limit (10 to 100000)> 1000
Up to 1000 the largest gap is 20, first between 887 and 907.
gap  how often
  1       1
  2      35
  4      40
  6      44
  8      15
 10      16
 12       7
 14       7
 18       1
 20       1

1) primes up to  2) prime factors  3) twin primes  4) Goldbach  5) gaps  6) quit
choice> 6
Bye.
```

## Modules

### main.eml

```eml
# P068 prime explorer: the primes up to a limit by the sieve of
# Eratosthenes, a number broken into prime factors, twin primes, the ways
# an even number is a sum of two primes, and the gaps between primes.
import primes

def trim(s):
    0 => i
    len(s) => j
    while i < j and s[i] == " ":
        i + 1 => i
    while j > i and s[j - 1] == " ":
        j - 1 => j
    return s[i:j]

def counted(k, one, many):
    if k == 1:
        return "1 " + one
    return str(k) + " " + many

def number(s):
    if s == "" or len(s) > 12:
        return -1
    0 => n
    for c in s:
        if not (c >= "0" and c <= "9"):
            return -1
        n * 10 + int(c) => n
    return n

def ask(prompt, low, high):
    while True:
        trim(input(prompt + " (" + str(low) + " to " + str(high) + ")> ")) => answer
        if answer == "":
            return -1
        number(answer) => n
        if n >= low and n <= high:
            return n
        ("Type a whole number from " + str(low) + " to " + str(high) + ".") ^0

def listed(xs, most):
    # The numbers with spaces, cut after `most` with how many more.
    "" => s
    for k in [0:len(xs) - 1]:
        if k == most:
            return s + " ... and " + str(len(xs) - most) + " more"
        if s != "":
            s + " " => s
        s + str(xs[k]) => s
    return s

def up_to():
    ask("limit", 2, 100000) => n
    if n == -1:
        "Cancelled." ^0
        return
    primes.primes_up_to(n) => ps
    (counted(len(ps), "prime", "primes") + " up to " + str(n) + ": " + listed(ps, 40)) ^0

def factor():
    ask("number", 2, 999999999999) => n
    if n == -1:
        "Cancelled." ^0
        return
    primes.factors(n) => fs
    "" => s
    for f in fs:
        if s != "":
            s + " x " => s
        s + str(f[0]) => s
        if f[1] > 1:
            s + "^" + str(f[1]) => s
    if len(fs) == 1 and fs[0][1] == 1:
        (str(n) + " is prime.") ^0
    else:
        (str(n) + " = " + s) ^0

def twin_primes():
    ask("limit", 5, 100000) => n
    if n == -1:
        "Cancelled." ^0
        return
    primes.twins(primes.primes_up_to(n)) => ts
    [] => shown
    for t in ts:
        shown + [str(t[0]) + "-" + str(t[1])] => shown
    (counted(len(ts), "twin prime pair", "twin prime pairs") + " up to " + str(n) + ": " + listed(shown, 20)) ^0

def goldbach():
    while True:
        ask("even number", 4, 100000) => n
        if n == -1:
            "Cancelled." ^0
            return
        if n % 2 == 0:
            break
        "Goldbach's question is about even numbers." ^0
    primes.goldbach(n, primes.sieve(n)) => ws
    [] => shown
    for w in ws:
        shown + [str(w[0]) + "+" + str(w[1])] => shown
    if len(ws) == 0:
        (str(n) + " is not a sum of two primes - that would answer Goldbach's question.") ^0
    else:
        (str(n) + " is a sum of two primes in " + counted(len(ws), "way", "ways") + ": " + listed(shown, 12)) ^0

def gap_report():
    ask("limit", 10, 100000) => n
    if n == -1:
        "Cancelled." ^0
        return
    primes.primes_up_to(n) => ps
    primes.gaps(ps) => g
    ("Up to " + str(n) + " the largest gap is " + str(g[0]) + ", first between " + str(g[1][0]) + " and " + str(g[1][1]) + ".") ^0
    "gap  how often" ^0
    for k in [1:g[0]]:
        if k in g[2]:
            str(k) => a
            while len(a) < 3:
                " " + a => a
            str(g[2][k]) => b
            while len(b) < 6:
                " " + b => b
            (a + "  " + b) ^0

"== Prime explorer ==" ^0
"Primes by the sieve of Eratosthenes, prime factors, twins, Goldbach sums and gaps." ^0
True => running
while running:
    "" ^0
    "1) primes up to  2) prime factors  3) twin primes  4) Goldbach  5) gaps  6) quit" ^0
    trim(input("choice> ")) => choice
    if choice == "1":
        up_to()
    elif choice == "2":
        factor()
    elif choice == "3":
        twin_primes()
    elif choice == "4":
        goldbach()
    elif choice == "5":
        gap_report()
    elif choice == "6":
        False => running
    else:
        "Pick a number from 1 to 6." ^0
"Bye." ^0
```

Python projection of main.eml:

```python
import primes

def trim(s):
    i = 0
    j = len(s)
    while i < j and s[i] == " ":
        i = i + 1
    while j > i and s[j - 1] == " ":
        j = j - 1
    return s[i:j]

def counted(k, one, many):
    if k == 1:
        return "1 " + one
    return str(k) + " " + many

def number(s):
    if s == "" or len(s) > 12:
        return -1
    n = 0
    for c in s:
        if not (c >= "0" and c <= "9"):
            return -1
        n = n * 10 + int(c)
    return n

def ask(prompt, low, high):
    while True:
        answer = trim(input(prompt + " (" + str(low) + " to " + str(high) + ")> "))
        if answer == "":
            return -1
        n = number(answer)
        if n >= low and n <= high:
            return n
        print("Type a whole number from " + str(low) + " to " + str(high) + ".")

def listed(xs, most):
    s = ""
    for k in range(0, len(xs)):
        if k == most:
            return s + " ... and " + str(len(xs) - most) + " more"
        if s != "":
            s = s + " "
        s = s + str(xs[k])
    return s

def up_to():
    n = ask("limit", 2, 100000)
    if n == -1:
        print("Cancelled.")
        return
    ps = primes.primes_up_to(n)
    print(counted(len(ps), "prime", "primes") + " up to " + str(n) + ": " + listed(ps, 40))

def factor():
    n = ask("number", 2, 999999999999)
    if n == -1:
        print("Cancelled.")
        return
    fs = primes.factors(n)
    s = ""
    for f in fs:
        if s != "":
            s = s + " x "
        s = s + str(f[0])
        if f[1] > 1:
            s = s + "^" + str(f[1])
    if len(fs) == 1 and fs[0][1] == 1:
        print(str(n) + " is prime.")
    else:
        print(str(n) + " = " + s)

def twin_primes():
    n = ask("limit", 5, 100000)
    if n == -1:
        print("Cancelled.")
        return
    ts = primes.twins(primes.primes_up_to(n))
    shown = []
    for t in ts:
        shown = shown + [str(t[0]) + "-" + str(t[1])]
    print(counted(len(ts), "twin prime pair", "twin prime pairs") + " up to " + str(n) + ": " + listed(shown, 20))

def goldbach():
    while True:
        n = ask("even number", 4, 100000)
        if n == -1:
            print("Cancelled.")
            return
        if n % 2 == 0:
            break
        print("Goldbach's question is about even numbers.")
    ws = primes.goldbach(n, primes.sieve(n))
    shown = []
    for w in ws:
        shown = shown + [str(w[0]) + "+" + str(w[1])]
    if len(ws) == 0:
        print(str(n) + " is not a sum of two primes - that would answer Goldbach's question.")
    else:
        print(str(n) + " is a sum of two primes in " + counted(len(ws), "way", "ways") + ": " + listed(shown, 12))

def gap_report():
    n = ask("limit", 10, 100000)
    if n == -1:
        print("Cancelled.")
        return
    ps = primes.primes_up_to(n)
    g = primes.gaps(ps)
    print("Up to " + str(n) + " the largest gap is " + str(g[0]) + ", first between " + str(g[1][0]) + " and " + str(g[1][1]) + ".")
    print("gap  how often")
    for k in range(1, g[0]+1):
        if k in g[2]:
            a = str(k)
            while len(a) < 3:
                a = " " + a
            b = str(g[2][k])
            while len(b) < 6:
                b = " " + b
            print(a + "  " + b)

print("== Prime explorer ==")
print("Primes by the sieve of Eratosthenes, prime factors, twins, Goldbach sums and gaps.")
running = True
while running:
    print("")
    print("1) primes up to  2) prime factors  3) twin primes  4) Goldbach  5) gaps  6) quit")
    choice = trim(input("choice> "))
    if choice == "1":
        up_to()
    elif choice == "2":
        factor()
    elif choice == "3":
        twin_primes()
    elif choice == "4":
        goldbach()
    elif choice == "5":
        gap_report()
    elif choice == "6":
        running = False
    else:
        print("Pick a number from 1 to 6.")
print("Bye.")
```

### primes.eml

```eml
# P068 prime explorer - the sieve, factoring, and what the primes up to a
# limit look like: twins, Goldbach's sums and the gaps between them.

def sieve(n):
    # The corpus case sieve-of-eratosthenes: start with every number from 2
    # to n marked prime, and for each prime p cross out p*p, p*p + p, ... -
    # smaller multiples were crossed out by smaller primes already. Returns
    # the list of flags, index = number.
    [True] * (n + 1) => flags
    False => flags[0]
    if n >= 1:
        False => flags[1]
    2 => p
    while p * p <= n:
        if flags[p]:
            p * p => m
            while m <= n:
                False => flags[m]
                m + p => m
        p + 1 => p
    return flags

def primes_up_to(n):
    # Counted first, then written into a list made at its full length -
    # growing a list by + in a loop would copy it at every prime.
    sieve(n) => flags
    0 => count
    for k in [2:n]:
        if flags[k]:
            count + 1 => count
    [0] * count => out
    0 => i
    for k in [2:n]:
        if flags[k]:
            k => out[i]
            i + 1 => i
    return out

def quotient(a, b):
    # a // b for a >= 0, b > 0, exact (a float would lose digits past 2^53).
    0 => q
    while a >= b:
        b => m
        1 => k
        while m + m <= a:
            m + m => m
            k + k => k
        a - m => a
        q + k => q
    return q

def factors(n):
    # The corpus case prime-factorization's trial division: divide out 2,
    # then odd numbers d while d * d <= what is left; what remains above 1 is
    # prime. Returns [[prime, power], ...].
    [] => out
    n => left
    2 => d
    while d * d <= left:
        0 => k
        while left % d == 0:
            quotient(left, d) => left
            k + 1 => k
        if k > 0:
            out + [[d, k]] => out
        if d == 2:
            3 => d
        else:
            d + 2 => d
    if left > 1:
        out + [[left, 1]] => out
    return out

def twins(ps):
    # Pairs of primes two apart, like 11 and 13.
    [] => out
    for i in [1:len(ps) - 1]:
        if ps[i] - ps[i - 1] == 2:
            out + [[ps[i - 1], ps[i]]] => out
    return out

def goldbach(n, flags):
    # Every way to write the even number n > 2 as a sum of two primes p + q
    # with p <= q.
    [] => out
    for p in [2:quotient(n, 2)]:
        if flags[p] and flags[n - p]:
            out + [[p, n - p]] => out
    return out

def gaps(ps):
    # [largest gap, the primes either side of its first appearance, how many
    # times each gap size occurs as a dict].
    0 => best
    [0, 0] => where
    {} => count
    for i in [1:len(ps) - 1]:
        ps[i] - ps[i - 1] => g
        if g in count:
            count[g] + 1 => count[g]
        else:
            1 => count[g]
        if g > best:
            g => best
            [ps[i - 1], ps[i]] => where
    return [best, where, count]
```

Python projection of primes.eml:

```python
def sieve(n):
    flags = [True] * (n + 1)
    flags[0] = False
    if n >= 1:
        flags[1] = False
    p = 2
    while p * p <= n:
        if flags[p]:
            m = p * p
            while m <= n:
                flags[m] = False
                m = m + p
        p = p + 1
    return flags

def primes_up_to(n):
    flags = sieve(n)
    count = 0
    for k in range(2, n+1):
        if flags[k]:
            count = count + 1
    out = [0] * count
    i = 0
    for k in range(2, n+1):
        if flags[k]:
            out[i] = k
            i = i + 1
    return out

def quotient(a, b):
    q = 0
    while a >= b:
        m = b
        k = 1
        while m + m <= a:
            m = m + m
            k = k + k
        a = a - m
        q = q + k
    return q

def factors(n):
    out = []
    left = n
    d = 2
    while d * d <= left:
        k = 0
        while left % d == 0:
            left = quotient(left, d)
            k = k + 1
        if k > 0:
            out = out + [[d, k]]
        if d == 2:
            d = 3
        else:
            d = d + 2
    if left > 1:
        out = out + [[left, 1]]
    return out

def twins(ps):
    out = []
    for i in range(1, len(ps)):
        if ps[i] - ps[i - 1] == 2:
            out = out + [[ps[i - 1], ps[i]]]
    return out

def goldbach(n, flags):
    out = []
    for p in range(2, quotient(n, 2)+1):
        if flags[p] and flags[n - p]:
            out = out + [[p, n - p]]
    return out

def gaps(ps):
    best = 0
    where = [0, 0]
    count = {}
    for i in range(1, len(ps)):
        g = ps[i] - ps[i - 1]
        if g in count:
            count[g] = count[g] + 1
        else:
            count[g] = 1
        if g > best:
            best = g
            where = [ps[i - 1], ps[i]]
    return [best, where, count]
```

## README

# P068 - Prime explorer

The primes up to a limit, by the sieve of Eratosthenes. A number up to
999,999,999,999 broken into its prime factors. The twin primes, the ways an
even number is a sum of two primes (Goldbach's question), and the gaps
between primes, with how often each gap occurs.

- `main.eml` - the menu, reading numbers, and the reports
- `primes.eml` - the sieve, the list of primes, factorisation, twins,
  Goldbach sums and gaps

How each part works:

- Sieve: as in the corpus case `sieve-of-eratosthenes`, start with every
  number marked prime, and for each prime p cross out p x p, p x p + p,
  and so on. Crossing out can start at p x p, because a smaller multiple of
  p has a smaller prime factor and is already crossed out. The list of
  primes is counted first and then filled, rather than grown one prime at
  a time.
- Prime factors: as in the corpus case `prime-factorization`, divide by 2
  as often as it goes, then by 3, 5, 7 and the odd numbers after, while
  d x d is at most what is left. Whatever is left above 1 then is prime.
  So a 12-digit number needs at most about 500,000 trial divisions:
  600851475143 = 71 x 839 x 1471 x 6857.
- Twin primes are primes two apart. Goldbach sums try every p from 2 to
  n/2 and keep those where the sieve marks both p and n - p prime.
- Gaps: the difference between each prime and the next, counted. Up to
  1000 the largest gap is 20, from 887 to 907.

What is checked: menu choices 1 to 6; a limit from 2 to 100,000 for the
primes, 5 to 100,000 for twins and 10 to 100,000 for gaps; a number from 2
to 999,999,999,999 to factor; an even number from 4 to 100,000 for
Goldbach. An empty answer cancels. Long lists show their first 40 primes,
20 twin pairs or 12 sums, and say how many more there are.

Sessions: `sessions/basic.in` gives:
- the 25 primes up to 100, and the 1229 up to 10,000;
- 600851475143, the prime 1000003, and 360 = 2^3 x 3^2 x 5;
- the 35 twin prime pairs up to 1000;
- the 6 ways of writing 100 as a sum of two primes;
- the gaps up to 1000: 167 of them, the largest 20.

`sessions/bad-input.in` gives:
- menu choices 0 and x;
- limits 1, 100001 and abc, then a cancel;
- the numbers 1 and 1,000,000,000,000 to factor, then a cancel;
- 7 for Goldbach (odd) and 2 (too small), then a cancel;
- 9 as a gap limit, then a cancel.

Built on the verified corpus cases `sieve-of-eratosthenes` (crossing out
multiples) and `prime-factorization` (trial division with multiplicity).