Number Theory Problems

tip

⭐ AoPS Online focus on Number Theory

Prime Numbers ~ Sieve of Eratosthenes

Refer: https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html

note

• creating a array of size = n[excluding n] or n+1[including n] with values true

• 1st for loop

  • i iterates from [2 ⇢ sqrt(n)] or [i*i<=n]
  • it means 1 goes till sqrt(n)
  • So, the 2nd for loop j will start from where 1st for loop can't check, i.e. in this case 1st for loop only checks till i*i <= n

---

• 2nd for loop (int j = i * i; j < n; j += i)
  • j iterates from i*i as elements before i*i are already iterated in 1st for loop
    • **WHY** `i*i` : _Example:_ if 2_multiples=2,4,6,8,10,12.. & 3_multiples=3,6,**9**,12,.. & 4_multiples=4,8,16,... & 5_multiples=5,10,15,20,**25**... .
    • here we can see that, some multiples of 3 are already marked false by 2, so we need only to start with 9, for 4 all mulltiples are false, similarly for 5 multiples before 25 are all marked false.
    • Therefore, we can see that for i we can start from i*i as i*2 would already be marked by 2, i*3 would already be marked by 3, i*4 would already be marked by 4. So, unmarked multiples start from i*i and then we do +=i for the next multiples i in j loop.
    • VIDEO EXPLANATION: https://youtu.be/QDFM7Mjk2mc?t=1499
  • So, as i will iterated from 2 ⇢ sqrt(n) or [i*i <= n]; then j will check for each multipe of i from i*i ⇢ n
  • for each multiple of i in j loop, we update j as j += i i.e. if i = 2 , j = 4; j += i ⇢⇢ 8, 16, 32 ...

caution

Time Complexity: O(n.log(log n))

/* Given an integer 'n', return the number of prime numbers that are strictly less than 'n'. */

int countPrimes(int n)
{
    int count = 0;
    vector<bool> is_prime(n, true); /* here 'is_prime' size is n BUT if question had asked [including n], then size smust be n+1 as index 0 is not accountable for prime numbers */
    if (n == 0) {
        return 0;
    }
    is_prime[0] = is_prime[1] = false;  /* as 1 & 0 are NOT prime */
    for (int i = 2; i <= sqrt(n); i++)  /* 'i' iterates from [2 ⇢ sqrt(n)] or [i*i<=n] */
    {
        if (is_prime[i]) /* if is_prime == true : only then we will check forita multiples otherwise false means its already NOT prime */
        {
            for (int j = i * i; j < n; j += i)   /* `j` iterates from `i*i` as elements before `i*i` are already iterated in **1st for loop** */
            /* for each multiple of **i** in **j loop**, we update **j** as `j += i` i.e. if **i = 2** , **j = 4**; `j += i ⇢⇢ 8, 16, 32 ..` */
                is_prime[j] = false;
        }
    }

    for (auto el : is_prime)
    {
        if (el == true)
        {
            ++count;
        }
    }

    return count;
}

Must Refer: Prime numbers for CP - Striver

Euclid's Algorithm

GCD

• https://www.youtube.com/watch?v=utZcJ0leZ_g

LCM

• https://www.youtube.com/watch?v=utZcJ0leZ_g