### Number Theory Part -3

### Euler's totient function

*Description:*

**phi(N)**counts the number of integers from

**1**to

**N**inclusive that are relatively prime to

**N**.

*Implemention:*let me remind you that

*factorization*is the way to represent given number as a product of primes. And it's easy to see that for every number such representation is unique. For example:

**8 = 2**

11 = 11

36 = 2

935 = 5 * 11 * 17

5136 = 2

^{3}11 = 11

36 = 2

^{2}* 3^{2}935 = 5 * 11 * 17

5136 = 2

^{4}* 3 * 107So, implemention is based on factorization:

```
int phi(int n) {
int res = n;
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
while (n % i == 0) {
n /= i;
}
res -= res / i;
}
}
if (n != 1) {
res -= res / n;
}
return res;
}
```

It works in **O(sqrt(N))**time. How to make it faster read further.

### Modification of Sieve of Eratosthenes for fast factorization

*Implemention:*let's see how we can factorize

**N**in

**O(sqrt(N))**time

```
vector<int> factorize(int n) {
vector<int> res;
for (int i = 2; i * i <= n; ++i) {
while (n % i == 0) {
res.push_back(i);
n /= i;
}
}
if (n != 1) {
res.push_back(n);
}
return res;
}
```

At every step we are looking for a minimal prime number that divides our current **N**. This is the main idea of Sieve's modification. Let's construct such array which in

**O(1)**time will give us this number:

```
int minPrime[n + 1];
for (int i = 2; i * i <= n; ++i) {
if (minPrime[i] == 0) { //if i is prime
for (int j = i * i; j <= n; j += i) {
if (minPrime[j] == 0) {
minPrime[j] = i;
}
}
}
}
for (int i = 2; i <= n; ++i) {
if (minPrime[i] == 0) {
minPrime[i] = i;
}
}
```

Now we can factorize **N**in

**O(log(N))**time using this modification:

```
vector<int> factorize(int n) {
vector<int> res;
while (n != 1) {
res.push_back(minPrime[n]);
n /= minPrime[n];
}
return res;
}
```

*Conditions:*you can implement this modification only if you're allowed to create an array of integers with size

**N**.

*Advices:*this approach is useful when you need to factorize a lot of times some not very large numbers. It's not necessary to build such modified Sieve in every problem where you need to factorize something. Moreover you can't build it for such large

**N**like

**10**or

^{9}**10**. So, use factorization in

^{12}**O(sqrt(N))**instead.

*Cool fact:*if factorization of

**N**is

**p**then

_{1}^{q1}* p_{2}^{q2}* ... * p_{k}^{qk}**N**has

**(q**distinct divisors.

_{1}+ 1) * (q_{2}+ 1) * ... * (q_{k}+ 1)### Sieve of Eratosthenes on the segment

Sometimes you need to find all primes not in range**[1...N]**but in range

**[L...R]**, where

**R**is large enough.

*Conditions:*you're allowed to create an array of integers with size

**(R - L + 1)**.

*Implemention:*

```
bool isPrime[r - l + 1]; //filled by true
for (long long i = 2; i * i <= r; ++i) {
for (long long j = max(i * i, (l + (i - 1)) / i * i); j <= r; j += i) {
isPrime[j - l] = false;
}
}
for (long long i = max(l, 2); i <= r; ++i) {
if (isPrime[i - l]) {
//then i is prime
}
}
```

The approximate comlexity is **O(sqrt(R) * const)**

*Advices:*again it's not necessary to build such Sieve if you need to check just several numbers for primality. Use the following function instead which works in

**O(sqrt(N))**for every number:

```
bool isPrime(int n) {
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
return false;
}
}
return true;
}
```

**Keep following the Blog for more posts like these to improve Algorithms , Competitive Programming and for Interview Preparations . Happy Coding !!**
## Comments

## Post a Comment