CryptoAssignment2025

📘 Prime Detector → Prime Computer (Modified Willans’ Formula)

1. Overview

This project implements a Prime Detector → Prime Computer pipeline inspired by Willans’ Formula for computing the n-th prime number.

Willans’ original formula uses Wilson’s Theorem, which relies on factorials and is extremely slow.
This project replaces that component with a faster trial-division prime detector, allowing a simplified and educational reconstruction of the formula in code.

The final program contains:

• A Prime Detector D(x)
• A Prime Counting Function π(m)
• A modified Willans-style n-th prime summation

This satisfies the requirement of constructing a Prime Computer from a Prime Detector.

---

2. How the Program Works

The logic is implemented inside:

class PrimeComputer:

2.1 Prime Detector — detector(x)

Returns:

• 1 if x is prime
• 0 if composite

Uses deterministic trial division up to sqrt(x).

Complexity:

O(√x)

---

2.2 Prime Counting Function — pi_function(m)

Computes:

[ \pi(m) = \sum_{j=1}^{m} D(j) ]

Counts how many primes ≤ m.

---

2.3 n-th Prime Computer — compute_nth_prime(n)

Implements the modified Willans summation:

[ p_n = 1 + \sum_{m=1}^{2^n} \left\lfloor \left( \frac{n}{1+\pi(m)} \right)^{1/n} \right\rfloor ]

Key idea:

• If π(m) < n → term = 1
• If π(m) ≥ n → term = 0 → summation stops early

This gives the n-th prime.

⚠️ Still slow for larger n due to the exponential bound.

---

4. How to Run

Option 1 — Terminal

Save as:

prime_computer.py

Run:

python prime_computer.py

Example:

Enter the value of n: 10
Result: The 10-th prime number is 29

---

Option 2 — Import in Python

from prime_computer import PrimeComputer

pc = PrimeComputer()
print(pc.compute_nth_prime(20))  # Output: 71

---

5. Complexity Analysis

Prime Detector

O(√x)

Prime Counting Function

O(m√m)

n-th Prime Computation

Worst-case upper bound:

2^n

🚨 Exponential growth → extremely slow for large n.

This matches Wilf’s argument that some formulas are mathematically correct but computationally useless.

---