Project 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.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-14
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
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 reportsprimes.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).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== 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.
What was typed (19 lines)
0
x
1
1
100001
abc
2
1
1000000000000
4
7
2
5
9
6
basic
interpreter: byte-equal== 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.
What was typed (17 lines)
1
100
1
10000
2
600851475143
2
1000003
2
360
3
1000
4
100
5
1000
6
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
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 (main.py)
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 (primes.py)
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]