Codeforces Round#511(Div.2),problem:(C)Enlarge GCD数論

まずanの値範囲内の素数を見つけて保存し、入力したデータの最大公倍数を求めてa配列を最大公倍数で割った後、anの値範囲(2から1は計算しない)を遍歴し、素数であればこの素数とその倍数を統計し、最小公倍数を増加させるために必要な数の個数である.巡回中に最小値を取ればいいです.特殊な状況を判定することに注意する.この方法はほとんどタイムアウトしそうだが、もっと良い方法があるようだが、私は思わなかった.
acコード:

#include 
#define FOR(I,A,B) for(int I = (A); I < (B); I++)
#define FORE(I,A,B) for(int I = (A); I <= (B); I++)
#define PRII pair 
#define LL long long 

#define INF 1000000001
#define N 200005
#define M 15000000
int gcd(int a,int b) { return b?gcd(b,a%b):a;}
using namespace std;
int a[300005];
int k[M],ss[M];
int main()
{
	int n;
	int ans = INF;
	cin >> n;
	cin >> a[1] >> a[2];
	bool fy = true;
	int agcd = gcd(a[1],a[2]);
	if(a[1] != a[2]) fy = false;
	FORE(i,3,n){
		cin >> a[i];
		agcd = gcd(a[i],agcd);
		if(a[i] != a[i-1]) fy = false;
	}
	FORE(i,2,int(sqrt(M)+1)){
		if(ss[i] == 0){
			for(int j = i*2;j <= M;j+=i) ss[j] = 1;
		}
	}
	FORE(i,1,n){
		k[a[i]/agcd]++;
	}