C++ Prime Number Finder Project
Test numbers for primality and generate every prime up to a limit.
What you will build
Check whether a number is prime, then scale up: find every prime below a limit. You'll discover why testing divisors only up to the square root matters, and meet the Sieve of Eratosthenes — a 2,300-year-old algorithm that still embarrasses naive loops.
What you will learn
- Trial division and the √n optimisation
- The Sieve of Eratosthenes
- Breaking out of loops early
- Thinking about algorithm speed, not just correctness
Feature checklist
- Primality test for a single number
- List all primes up to N
- Count of primes found (π(N))
- Uses the sieve for large N
- Times both methods so you can compare
Starter code
#include <iostream>
#include <vector>
#include <cmath>
bool isPrime(long long n) {
if (n < 2) return false;
if (n % 2 == 0) return n == 2;
for (long long d = 3; d * d <= n; d += 2) // only up to sqrt(n)
if (n % d == 0) return false;
return true;
}
std::vector<int> sieve(int limit) {
std::vector<bool> crossed(limit + 1, false);
for (int p = 2; 1LL * p * p <= limit; ++p)
if (!crossed[p])
for (int m = p * p; m <= limit; m += p) crossed[m] = true;
std::vector<int> primes;
for (int i = 2; i <= limit; ++i) if (!crossed[i]) primes.push_back(i);
return primes;
}
int main() {
auto primes = sieve(100);
std::cout << "Primes up to 100 (" << primes.size() << "):\n";
for (int p : primes) std::cout << p << " ";
std::cout << "\n999983 is prime? " << (isPrime(999983) ? "yes" : "no") << "\n";
}Full walkthrough
Step 1: Write isPrime() with trial division up to √n
A number n is prime if nothing from 2 to √n divides it evenly — any factor larger than √n would need a partner smaller than √n, which you would already have found. Handle the small cases explicitly: n < 2 is not prime, 2 and 3 are. Testing only EVEN candidates after 2 halves the work for free.
bool isPrime(long long n) {
if (n < 2) return false;
for (long long i = 2; i * i <= n; ++i)
if (n % i == 0) return false;
return true;
}Step 2: Use i * i <= n instead of sqrt in the loop
Comparing i * i <= n avoids calling std::sqrt on every iteration and sidesteps floating-point edge cases at perfect squares. Watch overflow for very large n: i * i can overflow a 32-bit int, which is why the parameter is long long.
Step 3: Build the sieve for the many-number question
sieve(int n) answers a different question — ALL primes up to n — with a std::vector<bool> crossed-out table: mark everything prime, then for each unmarked i, cross out its multiples starting at i*i. Multiples below i*i were already crossed by smaller factors, which is the optimisation that makes the sieve fly.
Step 4: Return the primes, not just the table
Collect the surviving indexes into a std::vector<int> and return it. Callers can then print them, count them (that count is π(N), the prime-counting function), or hand them to other code — a function that PRINTS its result can never be reused.
Step 5: Wire both tools into a menu
Option 1: test one number with isPrime(). Option 2: list all primes up to N with sieve(). Option 3 (the fun one): run BOTH on the same large N and time them with std::chrono — the checklist's comparison. Same input, two algorithms, wildly different clocks: that contrast is the real lesson of this project.
Step 6: Test against known values
π(30) = 10 (2, 3, 5, 7, 11, 13, 17, 19, 23, 29). 97 is prime, 91 is NOT (7 × 13 — the most falsely-believed prime), 1 is not prime. If sieve and isPrime ever disagree about a number, at least one is wrong — cross-checking your two implementations against each other is free verification.
Step 7: Feel the performance cliff
Time isPrime-per-number up to 1,000,000 versus sieve(1000000). The sieve wins by orders of magnitude because it shares work between numbers. Remember the shape of that result: algorithm choice beats code micro-tuning, nearly always.
Common mistakes
- Looping i up to n - 1 instead of √n, making large tests a hundred times slower for no benefit.
- Declaring 1 prime (or crashing on 0 and negatives) because the small cases were never handled.
- Starting the sieve's crossing-out at 2*i instead of i*i — correct but wasteful — or worse, crossing out i itself.
Compile and run
g++ -std=c++17 -o primes primes.cppSample run
$ ./primes
1) Test one number 2) List primes up to N 3) Race both methods
> 1
Number:
> 97
97 is prime.
> 1
Number:
> 91
91 is NOT prime (7 x 13).
> 2
Up to:
> 30
2 3 5 7 11 13 17 19 23 29
Found 10 primes (pi(30) = 10).
> 3
Up to:
> 1000000
Trial division, one by one: 1480 ms — 78498 primes
Sieve of Eratosthenes: 12 ms — 78498 primes
Same answer. The sieve is ~120x faster.Try it in your browser
No browser demo is included for this project. Build the C++ version below — that is the real program.