PROBLEM LINK:
PRACTICE
Editorialist: Shivam Kumar
DIFFICULTY:
MEDIUM
PREREQUISITES:
Euler Totient Function, Number Theory
PROBLEM:
Chef is very busy now-a-days. So, he has given you a task to find the total count of all the number starting from 1 to n which are co-primes with n . For eg:- if y = 7 then there are 6 numbers which are co-primes with 7 . The numbers are 1, 2, 3, 4, 5, 6 .
Note:- a is co-prime with b means gcd (a, b) = 1.
Constraints:
1 <= t <= 100
1 <= n <= 10^6
Input:
The first line contains a single integer t which denotes no of test cases. (1 <= t <=100) The second line contains a single integer n which denotes the range. (1 <= n <= 10^6).
Output:
Print the total count of all the numbers starting from 1 to n which are co-primes with n in the single line.
Example : 1
Input:
1
7
Output:
6
Example-2
Input:
1
5
Output:
4
Explanation:
Total 4 numbers are there which are co-primes with 5. The numbers are 1, 2, 3, 4.
EXPLANATION:
To find the total count of all the number starting from 1 to n which are co-primes with n is calculated using Euler’s totient function . The value of Euler’s totient function is calculated using Euler’s product formula which states that the value of totient functions is below the product of overall prime factors p of n.
The formula basically says that the value of Φ(n) is equal to n multiplied by product of (1 – 1/p) for all prime factors p of n. For example value of Φ(6) = 6 * (1-1/2) * (1 – 1/3) = 2.
First of all prime numbers within range 10^6 is stored in vector calculated using sieve of Eratosthenes. Then we find the prime numbers which are factors of n. Then we have used the above formula to calculate the total no of such numbers which are co-primes with n.
SOLUTION:
#include <bits/stdc++.h>
#define int long long int
using namespace std;
void sosmart()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
int32_t main()
{
sosmart();
vector<int> p(1000000, 1);
vector<int> prime;
for (int i = 2; i < 1000000; i++) {
if (p[i]) {
prime.push_back(i);
// cout << i << " ";
for (int j = i * i; j <= 1000000; j = j + i) {
p[j] = 0;
}
}
}
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
int total = n;
for(int i = 0; (i < prime.size() and prime[i] <= n); ++i) {
if(n % prime[i] == 0) {
total = total/prime[i];
total *= (prime[i]-1);
}
}
cout << total << "\n";
}
// end of code
return 0;
}