P161PROA - ROUND 1A - Số gần nguyên tố

P161PROA.CPP

#include <bits/stdc++.h>
#define BachNX
#define _for(i,a,b) for (int i=(a),_b_=(b),_d_=(a<b?1:-1);i!=_b_;i+=_d_)
 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
 
bool prime(int x) {
	int j = sqrt(x);
	for (int i = 2; i <= j; i++) {
		if (x % i == 0) {
			return false;
		}
	}
	return true;
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("output.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	LL x,n;
	cin >> n;
	while (n--) {
		cin >> x;
		LL t = sqrt(x);
		if (x == 1 || t*t != x || !prime(t)) {
			cout << "NO\n";
		} else {
			cout << "YES\n";
		}
	}
	return 0;
} 

P161PROA.MD

P161PROA - ROUND 1A - Số gần nguyên tố

Đề bài

Chúng ta đều biết số nguyên tố là số nguyên dương mà chỉ có duy nhất 2 ước phân biệt. Iron man luôn thích những cái đặc biệt và mới mẻ, và anh ra đưa ra 1 định nghĩa mới “Số gần nguyên tố” – là các số nguyên dương mà có đúng 3 ước phân biệt.
Bạn được cho 1 mảng có n phần tử, hãy kiểm tra xem từng phần tử trong mảng có phải là số gần nguyên tố hay không.

Solution

Để 1 số có đúng 3 ước phân biệt thì số đó phải là bình phương của 1 số nguyên tố. Vì chỉ như thế số đó mới có thể có 3 ước phân biệt là 1, nó và căn của nó (là 1 số nguyên tố).

Chú ý: Các phần tử mảng nhập vào có kích thước lên đến 10¹² lên các bạn phải dùng kiểu số nguyên long long để tính toán.