Visible Lattice Points

lattice.cpp

//https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1572
#include <cstdio>
#include <cstdlib>

using namespace std;

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }

int main() {

    int c, n;
    int pre[1005], rprime; pre[0] = 0;

    for(int i = 1; i <= 1000; i++) {
        rprime = 0;
        for(int j = 0; j < i; j++) {
            if(gcd(i,j) == 1) rprime++;
        }
        pre[i] = pre[i-1] + (2*rprime); 
    }
    
    for(int i = 1; i <= 1000; i++) pre[i]++;

    scanf("%d", &c);

    for(int i = 1; i <= c; i++) {
        scanf("%d", &n);
        printf("%d %d %d\n", i, n, pre[n]);
    }

    return 0;
}