答案为 n − φ ( n ) 

//tc is healthy, just do it
#include <bits/stdc++.h>
using namespace std;

template<class T> void checkmin(T &a,const T &b) { if (b<a) a=b; } 
template<class T> void checkmax(T &a,const T &b) { if (b>a) a=b; }

class MyVeryLongCake {
public:
    int cut( int n ) ;
};
int MyVeryLongCake::cut(int n) {
    int ans=n,i,n0=n;
    for(i=2;i*i<=n;i++)
     if (n%i==0){
        ans=ans/i*(i-1);
        while(n%i==0) n/=i;
     }
    if (n>1) ans=ans/n*(n-1);
    return n0-ans;
}