Kiểm tra số nguyên tố (Prime number ) trong C++

• • Thuật toán:
  • Nhắc lại công thức toán học:  số nguyên tố là tập hợp các số chỉ chia hết cho số 1 và chính nó.
  • Ví dụ : 2, 3, 5, 7, 11, 13, 17, 23,…đều được gọi là số nguyên tố.
  • Số 2 chính là số nguyên tố nhỏ nhất và cũng là số nguyên tố chẵn duy nhất.
  • Để kiểm tra số nguyên tố của dãy : 1 2 3 4 5 6 ; ta làm như sau:
  • dem =0;
  • Cho i chạy từ 1 đến 6
  • Nếu soKT mà chia hết cho i, tăng biến dem++
  • soKT là số nguyên tố, thì nó chỉ chia hết cho 1 và chính nó nên chỉ có dem = 2 mới thỏa điều kiện.
  • Ví dụ : soKT  là số 4 , ta thấy (4 chia hết cho 1, 4 chia hết cho 2 và 4 chia hết cho 4) nên dem = 3, vậy 4 không phải là số nguyên tố
  • Bảng mô tả thuật toán:
  • Code C++

 
#include <bits/stdc++.h>
using namespace std;

int KiemtraNT(int soKT){
    int dem = 0;
    for(int i = 1; i <= soKT; i++)
        {
            if(soKT % i == 0)
            {
                dem ++;
            }
        }
    if (dem ==2)
        {
            return 1; //day la so nguyen to
        }
    else
    {
            return 0;
    }
}
int main()
{
int soKT;
cin >> soKT;
cout << KiemtraNT(soKT) << endl;
return 0;
}