## What is a Prime Number?↵
↵
Anumber is **prime** if it has **no divisors except 1prime is an integer strictly larger than one that is divisible only by one and by itself**.↵
↵
So to check whether `n` is prime or not, the basic idea is:↵
↵
* Try all numbers from **2 → n-1**↵
* If any number divides `n`, then `n` is composite↵
* Otherwise, `n` is prime↵
↵
### Naive Code↵
↵
```cpp↵
bool is_prime(int n) {↵
if (n <= 1) return false;↵
for (int i = 2; i < n; i++) {↵
if (n % i == 0) return false;↵
}↵
return true;↵
}↵
```↵
↵
---↵
↵
# Optimization: Why Only Check Until √n ?↵
↵
Example: `n = 16`↵
↵
Divisors:↵
↵
* 1 × 16↵
* 2 × 8↵
* 4 × 4↵
* 8 × 2↵
* 16 × 1↵
↵
Notice something?↵
↵
After reaching `4 = sqrt(16)`, the divisors start repeating.↵
↵
✔️ This means we only need to check divisibility up to `sqrt(n)`.↵
↵
### Optimized Prime Check↵
↵
```cpp↵
#define ll long long↵
↵
bool is_prime(ll n) {↵
if (n <= 1) return false;↵
for (ll i = 2; i * i <= n; i++) {↵
if (n % i == 0) return false;↵
}↵
return true;↵
}↵
```↵
↵
---↵
↵
# The Sieve of Eratosthenes — O(n log log n)↵
↵
Imagine numbers from `2 → 20`:↵
↵
```↵
1 2 3 4↵
5 6 7 8↵
9 10 11 12↵
13 14 15 16↵
17 18 19 20↵
```↵
↵
### Idea↵
↵
1. Assume all numbers are prime↵
2. Start from 2↵
3. Eliminate all multiples of 2↵
4. Move to the next number that is still marked prime↵
5. Eliminate all its multiples↵
6. Continue…↵
↵
At the end, all remaining `true` entries are primes.↵
↵
### Sieve Code↵
↵
```cpp↵
const int N = 1e6 + 5;↵
vector<bool> prime(N, true);↵
↵
void sieve() {↵
prime[0] = prime[1] = false;↵
for (int i = 2; i * i < N; i++) {↵
if (prime[i]) {↵
for (int j = i * i; j < N; j += i) {↵
prime[j] = false;↵
}↵
}↵
}↵
}↵
```↵
↵
---↵
↵
# Complexity Intuition↵
↵
### Removing all multiples of:↵
↵
* 2 → n/2↵
* 3 → n/3↵
* 4 → n/4↵
* 5 → n/5↵
* …↵
* n → n/n↵
↵
Total work:↵
↵
```↵
n(1/2 + 1/3 + 1/4 + ... + 1/n) = n log(n)↵
```↵
↵
But composite numbers contribute less, giving final:↵
↵
### Sieve = **O(n log log n)**↵
↵
---↵
↵
# Get All Divisors of n in O(√n)↵
↵
```cpp↵
vector<ll> divisors(ll n) {↵
vector<ll> ret;↵
for (ll i = 1; i * i <= n; i++) {↵
if (n % i == 0) {↵
ret.push_back(i);↵
if (i != n / i) ret.push_back(n / i);↵
}↵
}↵
return ret;↵
}↵
```↵
↵
---↵
↵
# Count Prime Divisors for All Numbers (Divisor Sieve)↵
↵
```cpp↵
const int N = 1e6 + 5;↵
int d[N]; // d[i] = number of prime divisors of i↵
↵
void sieveDivisors() {↵
for (int i = 2; i < N; i++) {↵
if (d[i] == 0) { // i is prime↵
for (int j = i; j < N; j += i) {↵
d[j]++;↵
}↵
}↵
}↵
}↵
```↵
↵
---↵
↵
# Prime Factorization in O(√n)↵
↵
```cpp↵
vector<pair<ll, ll>> primeFactors(ll n) {↵
vector<pair<ll, ll>> ret;↵
for (ll i = 2; i * i <= n; i++) {↵
if (n % i == 0) {↵
ll cnt = 0;↵
while (n % i == 0) {↵
cnt++;↵
n /= i;↵
}↵
ret.push_back({i, cnt});↵
}↵
}↵
if (n != 1) ret.push_back({n, 1});↵
return ret;↵
}↵
```↵
↵
---↵
↵
# Conclusion↵
↵
You learned:↵
↵
Basic prime checking↵
↵
Optimizing with sqrt(n)↵
↵
Sieve of Eratosthenes↵
↵
Time complexity intuition↵
↵
Getting divisors↵
↵
Counting prime divisors↵
↵
Prime factorization↵
↵
↵
A
↵
So to check whether `n` is prime or not, the basic idea is:↵
↵
* Try all numbers from **2 → n-1**↵
* If any number divides `n`, then `n` is composite↵
* Otherwise, `n` is prime↵
↵
### Naive Code↵
↵
```cpp↵
bool is_prime(int n) {↵
if (n <= 1) return false;↵
for (int i = 2; i < n; i++) {↵
if (n % i == 0) return false;↵
}↵
return true;↵
}↵
```↵
↵
---↵
↵
# Optimization: Why Only Check Until √n ?↵
↵
Example: `n = 16`↵
↵
Divisors:↵
↵
* 1 × 16↵
* 2 × 8↵
* 4 × 4↵
* 8 × 2↵
* 16 × 1↵
↵
Notice something?↵
↵
After reaching `4 = sqrt(16)`, the divisors start repeating.↵
↵
✔️ This means we only need to check divisibility up to `sqrt(n)`.↵
↵
### Optimized Prime Check↵
↵
```cpp↵
#define ll long long↵
↵
bool is_prime(ll n) {↵
if (n <= 1) return false;↵
for (ll i = 2; i * i <= n; i++) {↵
if (n % i == 0) return false;↵
}↵
return true;↵
}↵
```↵
↵
---↵
↵
# The Sieve of Eratosthenes — O(n log log n)↵
↵
Imagine numbers from `2 → 20`:↵
↵
```↵
1 2 3 4↵
5 6 7 8↵
9 10 11 12↵
13 14 15 16↵
17 18 19 20↵
```↵
↵
### Idea↵
↵
1. Assume all numbers are prime↵
2. Start from 2↵
3. Eliminate all multiples of 2↵
4. Move to the next number that is still marked prime↵
5. Eliminate all its multiples↵
6. Continue…↵
↵
At the end, all remaining `true` entries are primes.↵
↵
### Sieve Code↵
↵
```cpp↵
const int N = 1e6 + 5;↵
vector<bool> prime(N, true);↵
↵
void sieve() {↵
prime[0] = prime[1] = false;↵
for (int i = 2; i * i < N; i++) {↵
if (prime[i]) {↵
for (int j = i * i; j < N; j += i) {↵
prime[j] = false;↵
}↵
}↵
}↵
}↵
```↵
↵
---↵
↵
# Complexity Intuition↵
↵
### Removing all multiples of:↵
↵
* 2 → n/2↵
* 3 → n/3↵
* 4 → n/4↵
* 5 → n/5↵
* …↵
* n → n/n↵
↵
Total work:↵
↵
```↵
n(1/2 + 1/3 + 1/4 + ... + 1/n) = n log(n)↵
```↵
↵
But composite numbers contribute less, giving final:↵
↵
### Sieve = **O(n log log n)**↵
↵
---↵
↵
# Get All Divisors of n in O(√n)↵
↵
```cpp↵
vector<ll> divisors(ll n) {↵
vector<ll> ret;↵
for (ll i = 1; i * i <= n; i++) {↵
if (n % i == 0) {↵
ret.push_back(i);↵
if (i != n / i) ret.push_back(n / i);↵
}↵
}↵
return ret;↵
}↵
```↵
↵
---↵
↵
# Count Prime Divisors for All Numbers (Divisor Sieve)↵
↵
```cpp↵
const int N = 1e6 + 5;↵
int d[N]; // d[i] = number of prime divisors of i↵
↵
void sieveDivisors() {↵
for (int i = 2; i < N; i++) {↵
if (d[i] == 0) { // i is prime↵
for (int j = i; j < N; j += i) {↵
d[j]++;↵
}↵
}↵
}↵
}↵
```↵
↵
---↵
↵
# Prime Factorization in O(√n)↵
↵
```cpp↵
vector<pair<ll, ll>> primeFactors(ll n) {↵
vector<pair<ll, ll>> ret;↵
for (ll i = 2; i * i <= n; i++) {↵
if (n % i == 0) {↵
ll cnt = 0;↵
while (n % i == 0) {↵
cnt++;↵
n /= i;↵
}↵
ret.push_back({i, cnt});↵
}↵
}↵
if (n != 1) ret.push_back({n, 1});↵
return ret;↵
}↵
```↵
↵
---↵
↵
# Conclusion↵
↵
You learned:↵
↵
Basic prime checking↵
↵
Optimizing with sqrt(n)↵
↵
Sieve of Eratosthenes↵
↵
Time complexity intuition↵
↵
Getting divisors↵
↵
Counting prime divisors↵
↵
Prime factorization↵
↵



