Skip to content

Instantly share code, notes, and snippets.

@ngobach
Last active September 6, 2016 19:22
Show Gist options
  • Save ngobach/ffd3c8438bd4d6c83d67ec826c1d6d36 to your computer and use it in GitHub Desktop.
Save ngobach/ffd3c8438bd4d6c83d67ec826c1d6d36 to your computer and use it in GitHub Desktop.
P161PROA - ROUND 1A - Số gần nguyên tố
#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 - 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 1012 lên các bạn phải dùng kiểu số nguyên long long để tính toán.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment