백준 2904 c++ 수학은 너무 쉬워

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

2904번: 수학은 너무 쉬워

---

문제

상근이의 할머니는 매우 유명한 수학자이다. 할머니는 매일 수학 문제로 상근이를 힘들게 한다. 할머니는 종이 N장에 숫자를 하나씩 쓴 다음 상근이에게 준다. 그 다음 상근이는 다음과 같이 문제를 풀어야 한다.

두 수 A와 B를 고르고, A를 나눌 수 있는 소수 X를 고른다. 그 다음, A를 지우고 A/X를 쓰고, B를 지우고 B×X를 쓴다.

상근이는 위의 행동을 무한히 반복할 수 있다. 할머니는 상근이가 만든 수를 보고 점수를 계산한다. 점수가 높을수록 할머니는 상근이에게 사탕을 많이 준다. 점수는 종이에 적혀있는 모든 수의 최대공약수이다.

상근이가 얻을 수 있는 가장 높은 점수를 구하는 프로그램을 작성하시오. 또, 그 점수를 얻으려면 최소 몇 번 해야 하는지도 구한다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100) 둘째 줄에는 종이에 적혀있는 수 N개가 주어진다. 수는 모두 1,000,000보다 작거나 같은 양의 정수이다.

출력

첫째 줄에 상근이가 얻을 수 있는 가장 큰 점수와 최소 몇 번 만에 그 점수를 얻을 수 있는지를 출력한다. 

---

#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;

int N;
bool isPrime[1000001];//소수 판별
vector<int> prime;

void Era()
{
	memset(isPrime, true, sizeof(isPrime));//일단 다 true로
	isPrime[0] = false;
	isPrime[1] = false;
	for (int i = 2; i <= 1000000; i++)
	{
		for (int j = i+i; j <= 1000000; j = j+i)
		{
			isPrime[j] = false;
		}
	}
	for (int i = 2; i <= 1000000; i++)
	{
		if (isPrime[i])
			prime.push_back(i);
	}
}

int main()
{
	Era();//에라토스테네스의 체 소수판별
	cin >> N;
	vector<int> card(N,0);//입력 받을 카드

	//전체적으로 해당 소수가 사용된 횟수
	vector<int>allPrimeCnt(prime.size(), 0);
	//2중 배열 numPrimeCount[a][b] = 3 // a번쨰 수를 소인수분해 했을 때 소수 b가 3개 있음
	vector<vector<int>> numPrimeCount(N, vector<int>(prime.size(), 0));

	for (int i = 0; i < N; i++)
	{
		cin >> card[i];
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < prime.size(); j++)
		{
			while (card[i] % prime[j] == 0)//소수로 나누어 떨어지면
			{
				allPrimeCnt[j]++;//해당 소수는 사용되었으므로 증가
				numPrimeCount[i][j]++;//해당 카드에 사용된 소수 증가
				card[i] = card[i] / prime[j];
			}
		}
	}

	int score = 1;//최대 점수
	int moveCount = 0;//소수 이동 카운트
	for (int i = 0; i < prime.size(); i++)
	{
		if (allPrimeCnt[i] / N > 0)//만약 소수를 N카드에 모두 분배할 수 있다면
		{
			int need = allPrimeCnt[i] / N;
			score = score * pow(prime[i],need);

			for (int j = 0; j < N; j++)
			{
				if (numPrimeCount[j][i] < need)
				{
					moveCount = moveCount + (need - numPrimeCount[j][i]);
				}
			}
		}
	}

	cout << score << " " << moveCount;
}