#include <stdio.h> #include <math.h> #define MAX (6000000) bool bPrime[MAX];
void InitPrime() { int nMax = sqrt((double)MAX) + 1; bPrime[0] = bPrime[1] = true; for (int i = 2; i <= nMax; ++i) { if (!bPrime[i]) { for (int j = 2 * i; j < MAX; j += i) { bPrime[j] = true; } } } }
bool IsPrime(long long nN) { if (nN < MAX)return !bPrime[nN]; long long nMax = sqrt((double)nN) + 1; for (int i = 2; i <= nMax; ++i) { if (nN % i == 0) return false; } return true; }
long long Euler(long long nN) { long long nAns = 1;
//printf("nN:%I64d,", nN); if (IsPrime(nN))nAns = nN - 1; else for (int i = 2; i <= nN; ++i) { if (nN % i == 0) { nAns *= i - 1; nN /= i; while (nN % i == 0) { nAns *= i; nN /= i; } if (IsPrime(nN)) { nAns *= nN - 1; break; } } }
//printf("nAns:%I64d\n", nAns); return nAns; }
int main() { long long nN;
InitPrime(); while (scanf("%I64d", &nN) == 1) { long long nAns = 0; long long nMax = sqrt((double)nN) + 1e-8; for (long long i = 1; i <= nMax; ++i) { if (nN % i == 0) { //printf("i:%I64d\n", i); nAns += i * Euler(nN / i); if (i * i != nN) nAns += (nN / i) * Euler(i); } } printf("%I64d\n", nAns); }