Analyze Prime Numbers
Select + apply right algo: primality, factorization, distribution. Verify computationally + relate to Prime Number Theorem.
Use When
- Int prime or composite?
- Complete prime factorization
- Count/list primes up to bound
- Verify PNT approx for range
- Investigate prime props in number-theoretic proof/compute
In
- Required: Int(s) to analyze, or bound for distribution
- Required: Task — primality, factorization, distribution
- Optional: Preferred algo (trial div, Miller-Rabin, Sieve Eratosthenes, Pollard's rho)
- Optional: Formal proof or computational verdict
- Optional: Out format (factor tree, prime list, count, table)
Do
Step 1: Determine Task
Classify → 1 of 3 + select algo path:
- Primality: Int n, prime?
- Factorization: Composite n, complete prime factorization
- Distribution: Bound N, analyze primes ≤ N (count, list, gaps, density)
Record task + in values.
→ Clear classification + in values recorded.
If err: Ambiguous ("analyze 60") → ask clarify primality vs factorization vs distribution. Default factorization for composites + primality confirm suspected primes.
Step 2: Primality Testing (if task = primality)
Test n prime, algo matched to size:
Trivial: n < 2 not prime. n = 2 or 3 prime. n even + n > 2 → composite.
Small n (<10^6): Trial division.
- Test div all primes p ≤ floor(sqrt(n)).
- Opt: test 2, then odd 3, 5, 7, ... or 6k +/- 1 wheel.
- No divisor → prime.
Large n (>=10^6): Miller-Rabin probabilistic.
- n - 1 = 2^s * d, d odd.
- Per witness a in {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}:
- Compute x = a^d mod n.
- x = 1 or x = n - 1 → pass.
- Else square x up to s - 1 times. x = n - 1 ever → pass.
- No pass → composite (a = witness).
- n < 3.317 * 10^24 → witnesses give deterministic result.
Record verdict: prime or composite + witness/cert.
Small primes (1st 25):
| Index |
Prime |
Index |
Prime |
Index |
Prime |
| 1 |
2 |
10 |
29 |
19 |
67 |
| 2 |
3 |
11 |
31 |
20 |
71 |
| 3 |
5 |
12 |
37 |
21 |
73 |
| 4 |
7 |
13 |
41 |
22 |
79 |
| 5 |
11 |
14 |
43 |
23 |
83 |
| 6 |
13 |
15 |
47 |
24 |
89 |
| 7 |
17 |
16 |
53 |
25 |
97 |
| 8 |
19 |
17 |
59 |
|
|
| 9 |
23 |
18 |
61 |
|
|
→ Definitive (prime/composite) + algo used + witnesses/divisors.
If err: Miller-Rabin "probably prime" + certainty needed → escalate deterministic (AKS or ECPP). Trial div too slow → Miller-Rabin.
Step 3: Factorization (if task = factorization)
Factor n completely → prime power decomposition:
Extract small factors by trial div:
- Divide 2 as many times as possible, record exponent.
- Divide odd primes 3, 5, 7, 11, ... up to cutoff (10^4 or sqrt(n) if small).
- After each div, update n → cofactor.
Cofactor > 1 + <10^12: Continue trial div ≤ sqrt(cofactor).
Cofactor >= 10^12: Pollard's rho.
- f(x) = x^2 + c (mod n), random c.
- Floyd cycle: x = f(x), y = f(f(y)).
- d = gcd(|x - y|, n) each step.
- 1 < d < n → non-trivial factor. Recurse d + n/d.
- d = n → retry diff c.
Verify: Multiply all prime factors + exponents = original n. Test each factor primality.
Present: n = p1^a1 * p2^a2 * ... * pk^ak, p1 < p2 < ... < pk.
Algo complexity:
| Algo |
Complexity |
Best for |
| Trial division |
O(sqrt(n)) |
n < 10^12 |
| Pollard's rho |
O(n^{1/4}) expected |
n up to ~10^18 |
| Quadratic sieve |
L(n)^{1+o(1)} |
n up to ~10^50 |
| GNFS |
L(n)^{(64/9)^{1/3}+o(1)} |
n > 10^50 |
→ Complete prime factorization canonical form + multiplication verified.
If err: Pollard's rho fails after many iters (cycle w/o non-trivial gcd) → try diff c (≥5 attempts). All fail → cofactor may be prime → confirm primality.
Step 4: Distribution Analysis (if task = distribution)
Distribution of primes up to N:
Generate via Sieve Eratosthenes:
- Bool array size N + 1, true.
- Set 0 + 1 false (not prime).
- Per p from 2 to floor(sqrt(N)):
- Still true → mark multiples p^2, p^2 + p, p^2 + 2p, ... false.
- Collect indices still true.
Count: pi(N) = primes up to N.
Compare w/ PNT:
- PNT approx: pi(N) ~ N / ln(N).
- Logarithmic integral: Li(N) = integral 2 to N of 1/ln(t) dt.
- Relative err: |pi(N) - N/ln(N)| / pi(N).
Analyze gaps (optional):
- Gaps between consecutive primes.
- Max gap, avg gap, twin primes (gap = 2).
- Avg gap near N ~ ln(N).
Present summary:
Bound N: 1,000,000
pi(N): 78,498
N/ln(N): 72,382
Li(N): 78,628
Relative error (N/ln(N)): 7.79%
Relative error (Li(N)): 0.17%
Max prime gap: 148 (between 492113 and 492227)
Twin primes: 8,169 pairs
→ Count + PNT compare + optional gap analysis.
If err: N too large in-mem sieve (N > 10^9) → segmented sieve processes range in blocks. Count only (no list) → Meissel-Lehmer for pi(N) direct.
Step 5: Verify Computationally
Cross-check via independent method:
Primality: Trial div used → verify quick Miller-Rabin (or vice versa). Known primes → check published tables or OEIS.
Factorization: Multiply factors + confirm = original. Independently test each claimed prime.
Distribution: Spot-check 3-5 numbers from sieve out for primality. Compare pi(N) published values (pi(10^k) k = 1, ..., 9).
Published pi(N):
| N |
pi(N) |
| 10 |
4 |
| 100 |
25 |
| 1,000 |
168 |
| 10,000 |
1,229 |
| 100,000 |
9,592 |
| 10^6 |
78,498 |
| 10^7 |
664,579 |
| 10^8 |
5,761,455 |
| 10^9 |
50,847,534 |
- Doc verification + method + outcome.
→ All results independently verified no discrepancies.
If err: Verification → discrepancy → re-run w/ extra checks (verbose trial div logging). Common: off-by-one sieve bounds, int overflow modular arithmetic, pseudoprime mistaken prime.
Check
Traps
Forget n = 1 not prime: Convention — 1 neither prime nor composite. Many algos silently misclassify.
Int overflow modular exp: Computing a^d mod n for Miller-Rabin, naive exp overflows. Use modular exp (repeated squaring + mod each step).
Sieve off-by-one: Mark composites starting p^2, not 2p. 2p wastes time but correct; p+1 wrong.
Pollard's rho cycle w/ d = n: gcd(|x - y|, n) = n → algo found trivial factor. Retry diff c not just starting pt.
Carmichael nums fooling Fermat: Nums like 561 = 3 * 11 * 17 pass Fermat primality all coprime bases. Always Miller-Rabin, not plain Fermat.
Confuse pi(n) w/ constant pi: Prime counting fn pi(n) + circle constant 3.14159 share notation. Ctx unambiguous.
→
solve-modular-arithmetic — underpins Miller-Rabin + factorization
explore-diophantine-equations — factorization prereq for solving many
formulate-quantum-problem — Shor's algo for factorization connects primes → quantum
1---2name: analyze-prime-numbers-103description: Analyze prime numbers using primality tests, factorization algorithms, prime distribution analysis, and sieve methods. Covers trial division, Miller-Rabin, Sieve of Eratosthenes, and the Prime Number Theorem. Use when determining whether an integer is prime or composite, finding prime factorizations, counting or listing primes up to a bound, or investigating prime properties within a number-theoretic proof or computation.4license: MIT5---67# Analyze Prime Numbers89Select + apply right algo: primality, factorization, distribution. Verify computationally + relate to Prime Number Theorem.1011## Use When1213- Int prime or composite?14- Complete prime factorization15- Count/list primes up to bound16- Verify PNT approx for range17- Investigate prime props in number-theoretic proof/compute1819## In2021- **Required**: Int(s) to analyze, or bound for distribution22- **Required**: Task — primality, factorization, distribution23- **Optional**: Preferred algo (trial div, Miller-Rabin, Sieve Eratosthenes, Pollard's rho)24- **Optional**: Formal proof or computational verdict25- **Optional**: Out format (factor tree, prime list, count, table)2627## Do2829### Step 1: Determine Task3031Classify → 1 of 3 + select algo path:32331. **Primality**: Int n, prime?342. **Factorization**: Composite n, complete prime factorization353. **Distribution**: Bound N, analyze primes ≤ N (count, list, gaps, density)3637Record task + in values.3839**→** Clear classification + in values recorded.4041**If err:** Ambiguous ("analyze 60") → ask clarify primality vs factorization vs distribution. Default factorization for composites + primality confirm suspected primes.4243### Step 2: Primality Testing (if task = primality)4445Test n prime, algo matched to size:46471. **Trivial**: n < 2 not prime. n = 2 or 3 prime. n even + n > 2 → composite.48492. **Small n (<10^6)**: Trial division.50 - Test div all primes p ≤ floor(sqrt(n)).51 - Opt: test 2, then odd 3, 5, 7, ... or 6k +/- 1 wheel.52 - No divisor → prime.53543. **Large n (>=10^6)**: Miller-Rabin probabilistic.55 - n - 1 = 2^s * d, d odd.56 - Per witness a in {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}:57 - Compute x = a^d mod n.58 - x = 1 or x = n - 1 → pass.59 - Else square x up to s - 1 times. x = n - 1 ever → pass.60 - No pass → composite (a = witness).61 - n < 3.317 * 10^24 → witnesses give deterministic result.62634. **Record verdict**: prime or composite + witness/cert.6465**Small primes (1st 25):**6667| Index | Prime | Index | Prime | Index | Prime |68|---|---|---|---|---|---|69| 1 | 2 | 10 | 29 | 19 | 67 |70| 2 | 3 | 11 | 31 | 20 | 71 |71| 3 | 5 | 12 | 37 | 21 | 73 |72| 4 | 7 | 13 | 41 | 22 | 79 |73| 5 | 11 | 14 | 43 | 23 | 83 |74| 6 | 13 | 15 | 47 | 24 | 89 |75| 7 | 17 | 16 | 53 | 25 | 97 |76| 8 | 19 | 17 | 59 | | |77| 9 | 23 | 18 | 61 | | |7879**→** Definitive (prime/composite) + algo used + witnesses/divisors.8081**If err:** Miller-Rabin "probably prime" + certainty needed → escalate deterministic (AKS or ECPP). Trial div too slow → Miller-Rabin.8283### Step 3: Factorization (if task = factorization)8485Factor n completely → prime power decomposition:86871. **Extract small factors by trial div**:88 - Divide 2 as many times as possible, record exponent.89 - Divide odd primes 3, 5, 7, 11, ... up to cutoff (10^4 or sqrt(n) if small).90 - After each div, update n → cofactor.91922. **Cofactor > 1 + <10^12**: Continue trial div ≤ sqrt(cofactor).93943. **Cofactor >= 10^12**: Pollard's rho.95 - f(x) = x^2 + c (mod n), random c.96 - Floyd cycle: x = f(x), y = f(f(y)).97 - d = gcd(|x - y|, n) each step.98 - 1 < d < n → non-trivial factor. Recurse d + n/d.99 - d = n → retry diff c.1001014. **Verify**: Multiply all prime factors + exponents = original n. Test each factor primality.1021035. **Present**: n = p1^a1 * p2^a2 * ... * pk^ak, p1 < p2 < ... < pk.104105**Algo complexity:**106107| Algo | Complexity | Best for |108|---|---|---|109| Trial division | O(sqrt(n)) | n < 10^12 |110| Pollard's rho | O(n^{1/4}) expected | n up to ~10^18 |111| Quadratic sieve | L(n)^{1+o(1)} | n up to ~10^50 |112| GNFS | L(n)^{(64/9)^{1/3}+o(1)} | n > 10^50 |113114**→** Complete prime factorization canonical form + multiplication verified.115116**If err:** Pollard's rho fails after many iters (cycle w/o non-trivial gcd) → try diff c (≥5 attempts). All fail → cofactor may be prime → confirm primality.117118### Step 4: Distribution Analysis (if task = distribution)119120Distribution of primes up to N:1211221. **Generate via Sieve Eratosthenes**:123 - Bool array size N + 1, true.124 - Set 0 + 1 false (not prime).125 - Per p from 2 to floor(sqrt(N)):126 - Still true → mark multiples p^2, p^2 + p, p^2 + 2p, ... false.127 - Collect indices still true.1281292. **Count**: pi(N) = primes up to N.1301313. **Compare w/ PNT**:132 - PNT approx: pi(N) ~ N / ln(N).133 - Logarithmic integral: Li(N) = integral 2 to N of 1/ln(t) dt.134 - Relative err: |pi(N) - N/ln(N)| / pi(N).1351364. **Analyze gaps** (optional):137 - Gaps between consecutive primes.138 - Max gap, avg gap, twin primes (gap = 2).139 - Avg gap near N ~ ln(N).1401415. **Present summary**:142143```text144Bound N: 1,000,000145pi(N): 78,498146N/ln(N): 72,382147Li(N): 78,628148Relative error (N/ln(N)): 7.79%149Relative error (Li(N)): 0.17%150Max prime gap: 148 (between 492113 and 492227)151Twin primes: 8,169 pairs152```153154**→** Count + PNT compare + optional gap analysis.155156**If err:** N too large in-mem sieve (N > 10^9) → segmented sieve processes range in blocks. Count only (no list) → Meissel-Lehmer for pi(N) direct.157158### Step 5: Verify Computationally159160Cross-check via independent method:1611621. **Primality**: Trial div used → verify quick Miller-Rabin (or vice versa). Known primes → check published tables or OEIS.1631642. **Factorization**: Multiply factors + confirm = original. Independently test each claimed prime.1651663. **Distribution**: Spot-check 3-5 numbers from sieve out for primality. Compare pi(N) published values (pi(10^k) k = 1, ..., 9).167168**Published pi(N):**169170| N | pi(N) |171|---|---|172| 10 | 4 |173| 100 | 25 |174| 1,000 | 168 |175| 10,000 | 1,229 |176| 100,000 | 9,592 |177| 10^6 | 78,498 |178| 10^7 | 664,579 |179| 10^8 | 5,761,455 |180| 10^9 | 50,847,534 |1811824. **Doc verification** + method + outcome.183184**→** All results independently verified no discrepancies.185186**If err:** Verification → discrepancy → re-run w/ extra checks (verbose trial div logging). Common: off-by-one sieve bounds, int overflow modular arithmetic, pseudoprime mistaken prime.187188## Check189190- [ ] Task correctly classified (primality, factorization, distribution)191- [ ] Algo appropriate for in size192- [ ] Trivial cases (n < 2, n = 2, even n) handled pre-general193- [ ] Primality verdicts definitive (not "probably prime" unqualified)194- [ ] Factorizations multiply back to original195- [ ] Every claimed prime factor tested primality196- [ ] Sieve bounds include sqrt(N) coverage197- [ ] PNT compare uses correct formula (N/ln(N) or Li(N))198- [ ] Results verified by independent method or published values199- [ ] Edge cases (n = 0, 1, 2, neg) addressed200201## Traps202203- **Forget n = 1 not prime**: Convention — 1 neither prime nor composite. Many algos silently misclassify.204205- **Int overflow modular exp**: Computing a^d mod n for Miller-Rabin, naive exp overflows. Use modular exp (repeated squaring + mod each step).206207- **Sieve off-by-one**: Mark composites starting p^2, not 2p. 2p wastes time but correct; p+1 wrong.208209- **Pollard's rho cycle w/ d = n**: gcd(|x - y|, n) = n → algo found trivial factor. Retry diff c not just starting pt.210211- **Carmichael nums fooling Fermat**: Nums like 561 = 3 * 11 * 17 pass Fermat primality all coprime bases. Always Miller-Rabin, not plain Fermat.212213- **Confuse pi(n) w/ constant pi**: Prime counting fn pi(n) + circle constant 3.14159 share notation. Ctx unambiguous.214215## →216217- `solve-modular-arithmetic` — underpins Miller-Rabin + factorization218- `explore-diophantine-equations` — factorization prereq for solving many219- `formulate-quantum-problem` — Shor's algo for factorization connects primes → quantum