P161PROA - ROUND 1A - Số Gần Nguyên Tố - Gists · GitHub

Skip to content Search Gists Search Gists All gists Back to GitHub Sign in Sign up Sign in Sign up Dismiss alert {{ message }}

Instantly share code, notes, and snippets.

ngobach/P161PROA.CPP Last active September 6, 2016 19:22 Show Gist options

• Download ZIP

• Star 0 (0) You must be signed in to star a gist
• Fork 0 (0) You must be signed in to fork a gist

• Embed Select an option
  • Embed Embed this gist in your website.
  • Share Copy sharable link for this gist.
  • Clone via HTTPS Clone using the web URL.

  No results found

  Learn more about clone URLs Clone this repository at <script src="https://gist.github.com/ngobach/ffd3c8438bd4d6c83d67ec826c1d6d36.js"></script>
• Save ngobach/ffd3c8438bd4d6c83d67ec826c1d6d36 to your computer and use it in GitHub Desktop.

Code Revisions 2 Embed Select an option

• Embed Embed this gist in your website.
• Share Copy sharable link for this gist.
• Clone via HTTPS Clone using the web URL.

No results found

Learn more about clone URLs Clone this repository at <script src="https://gist.github.com/ngobach/ffd3c8438bd4d6c83d67ec826c1d6d36.js"></script> Save ngobach/ffd3c8438bd4d6c83d67ec826c1d6d36 to your computer and use it in GitHub Desktop. Download ZIP P161PROA - ROUND 1A - Số gần nguyên tố Raw P161PROA.CPP This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters Show hidden characters

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

}

Raw 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 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 You can’t perform that action at this time.