Cho số nguyên dương N (N <= 2 tỷ). Hãy kiểm tra xem số N có phải là số nguyên tố không? Số nguyên tố là số tự nhiên có duy nhất hai ước là 1 và chính nó. Ví dụ: 7 là số nguyên tố vì chỉ có 2 ước là 1 và 7, còn 8 không là số nguyên tố vì 8 có nhiều hơn 2 ước là 1, 2, 4 và 8. INPUT: Một số nguyên dương N (N <= 2 tỷ) OUTPUT: Đưa ra thông báo YES nếu N là số nguyên tố, trong trường hợp ngược lại thì đưa ra thông báo NO làm bằng c++ nhé

#include <bits/stdc++.h>
#define No {cout << "NO"; return 0;}
#define Yes {cout << "YES"; return 0;}
using namespace std;
int main() {
    int n;
    cin >> n;
    if (n <= 1) No;
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0) No;
    Yes;
}

Số nguyên tố là số chỉ chia hết cho `1` và chính nó, tức không chia hết cho bất kì số nào trong phạm vi từ `2` đến `N-1`.

Do `N <= 2,000,000,000`, khá lớn nên ta cần lặp từ `2` đến `\sqrt(N)` và kiểm tra xem `N` có chia hết cho số nào trong phạm vi đó không.

Độ phức tạp của thuật toán này là `O(\sqrt{N})`.

$\\$

Code tham khảo:

#include <iostream>

using namespace std;

int main() {

  int n; cin >> n;
  for (int i=2; i*i<=n; ++i) if (n % i == 0) {
    cout << "NO";
    return 0;
  }
  cout << "YES";
  
}

$\\$
$\\$
\begin{array}{c|c|c}\color{#ffd710}{\texttt{\{}} \color{#8655d6}{\texttt{\{}}\ \ \color{#8cdcda}{\text{Daoanhviet96}}\ \ \color{#8655d6}{\texttt{\}}} \color{#ffd710}{\texttt{\}}}\end{array}