백준 2725 보이는 점의 개수 (C++)

2725번: 보이는 점의 개수

유클리드 호제법으로 최대 공약수를 구해 푸는 문제이다. 먼저 gcd를 구현하고 N = 1000까지 최대 공약수가 1인 값들을 true로 두는 배열을 구해주었다. 그리고 입력받은 N까지 개수를 구해 출력해주었다. 간단히 풀 수 있었던 문제였다.

#include <iostream>
#include <cstring>

using namespace std;

int C, N;
bool check[1001][1001];

int findGcd(int a, int b) {
    if (a % b == 0) {
        return b;
    }

    return findGcd(b, a % b);
}

void solution() {
    check[1][1] = true;

    for (int i = 1; i <= 1000; i++) {
        for (int j = 1; j <= 1000; j++) {
            if (findGcd(i, j) == 1) {
                check[i][j] = true;
            }
        }
    }
}

void result() {
    int res = 2;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (check[i][j]) res++;
        }
    }

    cout << res << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> C;

    solution();

    while (C--) {
        cin >> N;

        result();
    }

    return 0;
}