https://www.spoj.pl/problems/GCDEX/
#include <cstdio> using namespace std; const int N = 1000001; bool sifted[N] = {}; int primes[80000], nprimes = 0; long long gcdsum[N]; int main() { int n; gcdsum[0] = 0; gcdsum[1] = 1; for (int i = 2; i < N; ++i) { if (!sifted[i]) { primes[nprimes++] = i; gcdsum[i] = 2*i-1; } for (int j = 0; j < nprimes && i*primes[j] < N; ++j) { sifted[i*primes[j]] = true; if (i%primes[j] == 0) { int n = i*primes[j], m = 0, nn = 1; while (n%primes[j] == 0) n /= primes[j], ++m, nn *= primes[j]; gcdsum[i*primes[j]] = ((m+1)*nn-m*(nn/primes[j])) * gcdsum[n]; break; } gcdsum[i*primes[j]] = gcdsum[i]*gcdsum[primes[j]]; } } for (int i = 1; i < N; ++i) gcdsum[i] += gcdsum[i-1]-i; while (scanf("%d", &n), n) printf("%lld\n", gcdsum[n]); } -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.