fork download
copy 
  1. #include <iostream>
  2. #include <cmath>
  3.  
  4. using namespace std;
  5.  
  6. bool isPrime(long long x) {
  7.     if (x < 2) return false;
  8.     if (x == 2 || x == 3) return true;
  9.     if (x % 2 == 0 || x % 3 == 0) return false;
  10.     for (long long i = 5; i * i <= x; i += 6) {
  11.         if (x % i == 0 || x % (i + 2) == 0) return false;
  12.     }
  13.     return true;
  14. }
  15.  
  16. void solve() {
  17.     long long n;
  18.     cin >> n;
  19.  
  20.     // N! chia hết cho N * (N + 1) / 2
  21.     // 2 * (N - 1)! chia hết cho (N + 1)
  22.     // --> 2 chia hết cho (N + 1) hoặc (N - 1)! chia hết cho (N + 1)
  23.     // --> N = 1 thì 2 chia hết cho (N + 1)
  24.  
  25.     if (n == 1) {
  26.         cout << "YES" << endl;
  27.         return;
  28.     }
  29.  
  30.      // ta nhận thấy rằng nếu (N + 1) mà là số nguyên tố thì chắc chắn (N - 1)! sẽ không chia hết cho (N + 1)
  31.      // còn nếu không phải số nguyên tố thì (N + 1) có thể được phân tích thừa số nguyên tố từ các số <= N/2 
  32.      // --> lúc này thì các thừa số nguyên tố này có trong (N - 1)!
  33.     long long m = n + 1;
  34.     if (isPrime(m)) {
  35.         cout << "NO" << endl;
  36.     } else {
  37.         cout << "YES" << endl;
  38.     }
  39. }
  40.  
  41. int main() {
  42.     ios_base::sync_with_stdio(false);
  43.     cin.tie(NULL);
  44.  
  45.     int t;
  46.     if (cin >> t) {
  47.         while (t--) {
  48.             solve();
  49.         }
  50.     }
  51.  
  52.     return 0;
  53. }
  54.  
Success #stdin #stdout 0s 5328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OIhWRX
language:
C++14 (clang 8.0)
created:
9 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!