Day 02 / 100: Find Prime Numbers

The Problem

I was given a simple task:
"Find all prime numbers less than or equal to ( N ), where ( N <= 10^7)."

Sounds easy, right? Just loop through all numbers, check if each one is prime, and print them. But wait—there’s a catch.

The First Roadblock: Brute Force Isn't Enough

I started with the basic definition of a prime number:
A number is prime if it is only divisible by 1 and itself.

So, I thought:
"I’ll loop through all numbers up to ( N ), check divisibility, and print the primes."

But then reality hit me. Checking each number individually would take forever. Imagine looping through 10 million numbers, checking divisibility for each one. That’s brutally inefficient.

I needed a better approach.

Eliminating Multiples

I asked myself:
"Instead of checking each number one by one, can I eliminate non-prime numbers systematically?"

That’s when I discovered the Sieve of Eratosthenes, a brilliant algorithm that marks multiples of primes as non-prime, reducing unnecessary checks.

Here’s how it works, using ( N = 30 ) as an example:

Step 1: Start with a list of numbers

We have numbers from 2 to 30.

Step 2: Begin with the smallest prime (2)

• Mark all multiples of 2 as not prime:
  4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 are removed.

Step 3: Move to the next smallest unmarked number (3)

• Mark all multiples of 3 as not prime:
  6, 9, 12, 15, 18, 21, 24, 27, 30 are removed.

Step 4: Move to the next smallest unmarked number (5)

• Mark all multiples of 5 as not prime:
  10, 15, 20, 25, 30 are removed.

Step 5: Continue up to the square root of N (which, in our case, is about 5.47, so we stop at 5)

• The remaining unmarked numbers are prime:
  2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Instead of checking each number individually, I was eliminating entire groups of numbers at once. Huge efficiency boost!

Writing the Code

Once I understood the Sieve of Eratosthenes, I implemented it step by step:

#include <iostream>
#include <vector>

using namespace std;

vector<int> primeNumbersTillN(int N) {
    vector<bool> is_prime(N + 1, true);
    is_prime[0] = is_prime[1] = false; // 0 and 1 are not prime

    for (int i = 2; i * i <= N; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= N; j += i) {
                is_prime[j] = false;
            }
        }
    }

    vector<int> primes;
    for (int i = 2; i <= N; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
    }

    return primes;
}

Why This Works So Well

• Instead of checking each number individually, we eliminate multiples in bulk.

• We only loop up to the square root of N, reducing unnecessary work.

The Key Takeaway

This journey wasn’t just about finding prime numbers. It was about:

• Getting stuck and realizing brute force wasn’t enough.

• Falling into a rabbithole of inefficient solutions.

• Discovering a smarter approach (Sieve of Eratosthenes).

• Scaling through by implementing the right algorithm.

This is what problem-solving is all about. It’s not just about knowing the answer, it’s about thinking through the problem, struggling, and finding a way forward.

Final Words

If you’re reading this as a recruiter, know that I don’t just write code. I think through problems.
If you’re reading this as my future kid, remember: getting stuck is part of the journey.
If you’re reading this as a curious guest, I hope you found this problem as fascinating as I did!

The real skill isn’t knowing the answer—it’s knowing how to find it.