Open this lesson in your favourite AI. It'll walk you through the why, explain the demo, and quiz you on the try-it list.
Primes are the multiplicative atoms of the integers — every integer is either prime or a product of primes, and that statement is the load-bearing wall under all of public-key cryptography. RSA's security rests on the empirical fact that you can multiply two large primes together quickly but not easily factor the result. Diffie-Hellman lives in for prime. Hash functions reduce modulo a prime to get well-mixed residue classes. Before any of that, you need to know what a prime is, why there are infinitely many, and why primality testing is fundamentally easier than factoring. This task is where you make that distinction concrete.
An integer is prime if its only positive divisors are 1 and . Otherwise, if has a divisor with , it's composite. The number 1 is neither (a deliberate convention — including 1 as prime would break the uniqueness in the fundamental theorem of arithmetic). Euclid's proof, written ~300 BC, shows there are infinitely many primes: assume there are finitely many , then has a prime factor not in the list — contradiction.
list(primerange(2, 100)). There should be 25 primes below 100.is_prime_naive to find the smallest prime above 1000. Then compute it with nextprime(1000) from sympy and confirm they match.is_prime_naive(10**12 + 39) versus isprime(10**12 + 39). The naive version should be visibly slower — that gap widens dramatically as the input grows, which is why cryptographic primality tests use Miller-Rabin or AKS, not trial division.Use these three in order. Each builds on the one before.
In one paragraph, define prime and composite numbers and explain why we deliberately exclude 1 from being prime. Then state Euclid's theorem and give the punchline of his proof.
Walk me step by step through Euclid's proof that there are infinitely many primes. Where does the contradiction come from, and which step relies on the fundamental theorem of arithmetic (or a weaker form of it)?
Why is primality testing in the complexity class P (since AKS in 2002), but factoring is conjecturally not? What's the structural difference between 'is $n$ prime?' and 'what are the prime factors of $n$?', and why does RSA rely on exactly this gap?
primerange. (Two consecutive primes with .) Prime gaps are central to several open conjectures in analytic number theory.// main.go — run: go run main.go
package main
import (
"fmt"
"math"
"math/big"
)
// Trial division — slow for big n, fine for small
func isPrimeNaive(n int) bool {
if n < 2 {
return false
}
if n < 4 {
return true
}
if n%2 == 0 {
return false
}
limit := int(math.Isqrt(uint(n)))
for d := 3; d <= limit; d += 2 {
if n%d == 0 {
return false
}
}
return true
}
func primesUpTo(max int) []int {
var out []int
for n := 2; n < max; n++ {
if isPrimeNaive(n) {
out = append(out, n)
}
}
return out
}
func primeRange(lo, hi int) []int {
var out []int
for n := lo; n < hi; n++ {
if isPrimeNaive(n) {
out = append(out, n)
}
}
return out
}
func nextPrime(n *big.Int) *big.Int {
c := new(big.Int).Add(n, big.NewInt(1))
for {
// big.Int.ProbablyPrime uses Miller-Rabin (20 rounds)
if c.ProbablyPrime(20) {
return c
}
c.Add(c, big.NewInt(1))
}
}
func main() {
fmt.Println(primesUpTo(30))
// [2 3 5 7 11 13 17 19 23 29]
// big.Int.ProbablyPrime uses Miller-Rabin and is fast on huge inputs
n := new(big.Int)
n.SetString("1000000000000000009", 10) // 10^18 + 9
fmt.Println(n.ProbablyPrime(20)) // true
fmt.Println(primeRange(100, 130)) // [101 103 107 109 113 127]
base := new(big.Int).Exp(big.NewInt(10), big.NewInt(100), nil)
fmt.Println(nextPrime(base)) // next prime above 10^100
}go run main.go