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; }