UVa 10179 - Irreducable Basic Fractions Solution

#include <iostream>
#include <vector>
#include <bitset>
#include <cmath>
using namespace std;
bitset<31624> p;
vector<int> prime;
void calc(){
    int tmp=31623;
    int tmp2=178;
    for(int i=2;i<=tmp;i++){
        if(!p[i]){
            prime.push_back(i);
            if(i<=tmp2)
                for(int j=i*i;j<=tmp;j+=i)
                    p[j]=1;
            }
        }
    }
int main(){
    calc();
    ios::sync_with_stdio(0);
    int n;
    while(cin>>n&&n){
        int N=n;
        int ans=n;
        for(int i=0;i<prime.size()&&prime[i]<=sqrt(N)&&n>1;i++){
            if(n%prime[i]==0){
                while(n%prime[i]==0)
                    n/=prime[i];
                ans/=prime[i];
                ans*=prime[i]-1;
            }
        }
        if(n>1){
            ans/=n;
            ans*=n-1;
        }
        cout<<ans<<endl;
    }
}