Algorithm
Problem link- https://www.spoj.com/problems/ETF/
ETF - Euler Totient Function
| English | Vietnamese |
In number theory, the totient φ of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n.
Given an integer n (1 <= n <= 10^6). Compute the value of the totient φ.
Input
First line contains an integer T, the number of test cases. (T <= 20000)
T following lines, each contains an integer n.
Output
T lines, one for the result of each test case.
Example
Input: 5 1 2 3 4 5 Output: 1 1 2 2 4
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
#include <limits.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
#define MOD (ll)1000000007
#define pb push_back
#define EPS 1e-9
#define FOR(i, n) for(int i = 0;i < n; i++)
#define pi(a) printf("%d\n", a)
#define all(c) c.begin(), c.end()
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define gc getchar_unlocked
template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
void si(int &x){
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 || c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
const int MAXN = 1e6+5;
int minPrime[MAXN];
void sieve(){
minPrime[1] = 1;
for(int i = 2; i*i <= MAXN; i++){
if(minPrime[i] == 0){
if(i*(ll)1*i <= MAXN){
for(int j = i*i; j <= MAXN; j += (i)){
if(minPrime[j] == 0)
minPrime[j] = i;
}
}
}
}
for(int i = 2;i <= MAXN; i++){
if(minPrime[i] == 0)
minPrime[i] = i;
}
}
/* Time Complexity - O(logN + nloglogN> */
vector<int> factors;
ll eulerPhi(int n){
set<int> s;
ll res = n;
while(n!=1){
if(s.empty() || s.find(minPrime[n]) == s.end()){
res = res-res/minPrime[n];
s.insert(minPrime[n]);
}
n/=minPrime[n];
}
return res;
}
int main(int argc, char const *argv[]){
int t;
si(t);
sieve();
while(t--){
int n;
si(n);
printf("%lld\n", eulerPhi(n));
}
return 0;
}Input
5
1
2
3
4
5
1
2
3
4
5
Output
1
1
2
2
4
1
2
2
4
#2 Code Example with Java Programming
Code -
Java Programming
import java.lang.StringBuilder;
import java.io.DataInputStream;
import java.io.IOException;
final class Reader{
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream dis;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Reader(){
dis = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public void omitLines(int n) throws IOException{
while (n > 0){
if (read() == '\n')
n--;
}
}
public int nextInt() throws IOException{
int ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do{
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public long nextPositiveLong() throws IOException{
long ret = 0;
byte c = read();
while (c <= ' ')
c = read();
do{
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
return ret;
}
public int nextPositiveInt() throws IOException{
int ret = 0;
byte c = read();
while (c <= ' ')
c = read();
do{
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
return ret;
}
private void fillBuffer() throws IOException{
bytesRead = dis.read(buffer, bufferPointer = 0, BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
private byte read() throws IOException{
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
public void close() throws IOException{
if (dis == null)
return;
dis.close();
}
}
final class ETF{
final static int [] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997};
public static int phi(int n){
int result = n;
for (int p : primes){
if (p*p > n) break;
if (n % p == 0){
result -= result/p;
n /= p;
while (n % p == 0){
n /= p;
}
}
}
if (n > 1){
result -= result/n;
}
return result;
}
public static void main(String args[]) throws IOException{
Reader r = new Reader();
StringBuilder sb = new StringBuilder();
int T = r.nextPositiveInt(), n;
while (T-- > 0){
n = r.nextPositiveInt();
sb.append(phi(n));
sb.append('\n');
}
System.out.print(sb.toString());
}
}Input
5
1
2
3
4
5
1
2
3
4
5
Output
1
1
2
2
4
1
2
2
4
Demonstration
SPOJ Solution-Euler Totient Function-Solution in C, C++, Java, Python