# Number Theory Basics — Primes, Optimization & Sieve
Разница между en1 и en2, 16 символ(ов) изменены
##  What is a Prime Number?↵
↵
A number is **prime** if it has **no divisors except 1 and 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↵
↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Nourhan_Abo-Heba 2025-11-29 13:47:19 81
en2 Английский Nourhan_Abo-Heba 2025-11-26 17:38:50 16
en1 Английский Nourhan_Abo-Heba 2025-11-26 17:37:45 3385 Initial revision (published)