백준 2725번 : 보이는 점의 개수 (c++)

https://www.acmicpc.net/problem/2725

2725번: 보이는 점의 개수

문제

(0,0)에서 보이는 (x,y)의 개수를 구하려고 한다.(x,y >= 0, 정수)

(0,0)에서 (x,y)가 보이려면 (0,0)과 (x,y)를 연결하는 직선이 다른 점을 통과하지 않아야 한다. 예를 들어 (4,2)는 (0,0)에서 보이지 않는다. 그 이유는 (0,0)과 (4,2)를 연결하는 직선이 (2,1)을 통과하기 때문이다. 아래 그림은 0 <= x,y<=5인 경우에 (0,0)에서 보이는 점의 개수이다. 단, (0,0)은 계산하지 않는다.

N이 주어졌을 때, 원점에서 보이는 (x,y) 좌표의 개수를 출력하시오. (0 <= x,y <= N)

입력
첫째 줄에 테스트 케이스의 개수 C(1<=C<=1,000)가 주어진다. 각 테스트 케이스는 자연수 N(1<=N<=1,000) 하나로 이루어져 있고, 한 줄에 하나씩 주어진다.

출력
각 테스트 케이스에 대해 한 줄에 하나씩 (0,0)에서 보이는 점(x,y)의 개수를 출력한다.

확인
p1^m*p2^n의 서로소의 값은 (p1^m-p1^(m-1)) * (p2^n-p2^(n-1))

예제 입력 1 
4
2
4
5
231
예제 출력 1 
5
13
21
32549

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;
int C, N;

int arr[1001];
int ans[1001];
vector <int> prime;
int main() {
	freopen("input.txt", "r", stdin);
	cin >> C;
	
	for (int i = 2; i <= 1000; i++) {
		if (arr[i] == 0) {
			prime.push_back(i);
			for (int j = 2; i*j <=1000 ; j++)
			{
				if (arr[i * j] == 0) {
					arr[i * j] = 1;
				}
			}
		}
	}

	for (int i = 2; i <= 1000; i++)
	{
		int chk = 0;
		int pi = 1;
		int cnt = 0;
		int k = i;
		int temp = 0;
		while (k != 1&&temp!=1) {
			if (k % prime[chk] == 0) {
				k /= prime[chk];
				cnt++;
			}
			else {
				if (cnt != 0) {
					pi *= pow(prime[chk], cnt) - pow(prime[chk], cnt - 1);
					cnt = 0;
				}
				chk++;
			}
		}
		pi *= pow(prime[chk], cnt) - pow(prime[chk], cnt - 1);
		ans[i] = ans[i - 1] + pi;
	}

	while (C--) {
		cin >> N;
		cout << ans[N] * 2 + 3 << "\n";
	}
	return 0;
}