Maximum Winter Contest 2008 H問題(Problem H Hidden Prime Number)

『Maximum Winter Contest 2008』のH問題
http://maximum.vc/PastProblems/Winter-Contest-2008/h/h.html

エラストテネスの篩で2-16までのテーブルを作って、ユークリッドの互除法(GCD)で求めたものがソスウ化判定するだけ

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

#define MAX 100000

int main(){
	int i, j, f;
	unsigned long long x, y, t;
	char *pri;

	pri = new char[MAX];
	memset(pri, 1, MAX);
	pri[0] = pri[1] = 0;
	for(i = 2; i < sqrt(MAX) + 1; i++)
		if(pri[i])
			for(j = i * 2; j < MAX; j += i)
				pri[j] = 0;

	while(scanf("%llu %llu", &x, &y), (x || y)){
		if(x < y){
			t = x;
			x = y;
			y = t;
		}
		while(y != 0 && x % y){
			t = x % y;
			x = y;
			y = t;
		}
		if(y >= MAX){
			for(i = f = 0; i < MAX && i <= sqrt(y) + 1 && f == 0; i++)
				if(pri[i] && y % i == 0)f = 1;
			if(f)cout << "No" << endl;
			else cout << "Yes" << endl;
		}else{
			if(pri[y])cout << "Yes" << endl;
			else cout << "No" << endl;
		}
	}

	delete pri;

	return 0;
}