A prime is an integer greater than 1 whose only positive divisors are 1 and itself. Every integer greater than 1 factors uniquely into primes. There are infinitely many of them.
Fundamental theorem of arithmetic
Every integer n > 1 can be written as a product of primes, and this factorization is unique up to the order of factors. This is the structural backbone of number theory: the primes are the atoms.
Scheme
; Prime factorization
(define (factor n)
(define (factor-helper n d)
(cond ((> (* d d) n) (if (> n 1) (list n) (list)))
((= 0 (modulo n d))
(cons d (factor-helper (quotient n d) d)))
(else (factor-helper n (+ d 1)))))
(factor-helper n 2))
(display "factor(60) = ") (display (factor 60)) (newline)
(display "factor(97) = ") (display (factor 97)) (newline)
(display "factor(360) = ") (display (factor 360)) (newline)
(display "factor(1024) = ") (display (factor 1024))
Python
# Prime factorizationdef factor(n):
factors = []
d = 2while d * d <= n:
while n % d == 0:
factors.append(d)
n //= d
d += 1if n > 1:
factors.append(n)
return factors
print(f"factor(60) = {factor(60)}")
print(f"factor(97) = {factor(97)}")
print(f"factor(360) = {factor(360)}")
print(f"factor(1024) = {factor(1024)}")
Infinitude of primes (Euclid's proof)
Suppose there are only finitely many primes p1, p2, ..., pn. Consider N = p1 p2 ... pn + 1. No pi divides N (each leaves remainder 1). So N has a prime factor not in the list. Contradiction. Therefore, there are infinitely many primes.
Scheme
; Euclid's proof, constructively:; Given a list of primes, find a new one.
(define (euclid-new-prime known-primes)
(let* ((product (apply * known-primes))
(n (+ product 1)))
; n might not be prime itself, but its smallest; prime factor is not in known-primes.
(define (smallest-factor n d)
(cond ((> (* d d) n) n)
((= 0 (modulo n d)) d)
(else (smallest-factor n (+ d 1)))))
(smallest-factor n 2)))
(display "Start with (2,3): new prime = ")
(display (euclid-new-prime (list 23))) (newline)
; 2*3+1 = 7, which is prime
(display "Start with (2,3,5): new prime = ")
(display (euclid-new-prime (list 235))) (newline)
; 2*3*5+1 = 31, which is prime
(display "Start with (2,3,5,7,11,13): new prime = ")
(display (euclid-new-prime (list 23571113)))
; 30031 = 59 * 509; smallest new prime is 59
Sieve of Eratosthenes
To find all primes up to n: list 2 through n, then cross out multiples of 2 (keeping 2), multiples of 3 (keeping 3), and so on. Whatever remains is prime. You only need to sieve up to the square root of n.
Scheme
; Sieve of Eratosthenes
(define (sieve n)
(let ((is-prime (make-vector (+ n 1) #t)))
(vector-set! is-prime 0#f)
(vector-set! is-prime 1#f)
(let loop ((i 2))
(when (<= (* i i) n)
(when (vector-ref is-prime i)
(let inner ((j (* i i)))
(when (<= j n)
(vector-set! is-prime j #f)
(inner (+ j i)))))
(loop (+ i 1))))
; collect primes
(let collect ((i 2) (primes (list)))
(if (> i n)
(reverse primes)
(collect (+ i 1)
(if (vector-ref is-prime i)
(cons i primes)
primes))))))
(display "Primes up to 50: ")
(display (sieve 50))
Python
# Sieve of Eratosthenesdef sieve(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
i = 2while i * i <= n:
if is_prime[i]:
for j inrange(i * i, n + 1, i):
is_prime[j] = False
i += 1return [i for i inrange(2, n + 1) if is_prime[i]]
print(f"Primes up to 50: {sieve(50)}")
Neighbors
→ Cryptography Ch.6 — RSA encryption relies on the difficulty of factoring large numbers into primes