Bài tập kiểm tra số nguyên tố trong C++
Kiểm tra số nguyên tố ít gặp trong thực tế công việc và cuộc sống nhưng trong quá trình học lập trình các bạn có thể sẽ phải gặp khá nhiều vì dạng toán rất phù hợp với ngôn ngữ lập trình cơ bản. Tùy vào những thuật toán của người dùng mà bài toán về số nguyên tố này sẽ có những chỗ hơi khác nhau.
Trong bài này mình sẽ giới thiệu các bạn hàm kiểm tra số nguyên tố chuẩn nhất và ngắn nhất. Trước tiên chúng ta sẽ phải định nghĩa Số nguyên tố là gì?
Số nguyên tố là số chỉ có 2 ước số dương phân biệt là 1 và chính nó. Hay nói cách khác nó chỉ chia hết cho chính nó và 1 nhưng trừ số 0 và 1 ra. Vì số 0 và 1 chỉ có 1 ước số là 1.
Những số nguyên tố nhỏ hơn 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
Thực tế để bài toán tối ưu hơn thì chúng ta sẽ không cho dòng chạy for chạy từ 2 tới n/2 mà chạy từ 2 tới căn của n như sau:
Xem thêm: Bài tập C++: Viết chương trình, hàm kiểm tra số chính phương
Kiểm tra số nguyên tố ít gặp trong thực tế công việc và cuộc sống nhưng trong quá trình học lập trình các bạn có thể sẽ phải gặp khá nhiều vì dạng toán rất phù hợp với ngôn ngữ lập trình cơ bản. Tùy vào những thuật toán của người dùng mà bài toán về số nguyên tố này sẽ có những chỗ hơi khác nhau.
Trong bài này mình sẽ giới thiệu các bạn hàm kiểm tra số nguyên tố chuẩn nhất và ngắn nhất. Trước tiên chúng ta sẽ phải định nghĩa Số nguyên tố là gì?
Số nguyên tố là số chỉ có 2 ước số dương phân biệt là 1 và chính nó. Hay nói cách khác nó chỉ chia hết cho chính nó và 1 nhưng trừ số 0 và 1 ra. Vì số 0 và 1 chỉ có 1 ước số là 1.
Những số nguyên tố nhỏ hơn 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
Mã:
#include <iostream>
using namespace std;
int kiemTraSoNguyenTo(int);
int main()
{
int n;
cout << "Nhap vao 1 so nguyen: ";
cin >> n;
if(kiemTraSoNguyenTo(n)==0)
cout << n << " la so nguyen to";
else
cout << n << " khong phai la so nguyen to.";
return 0;
}
int kiemTraSoNguyenTo(int n)
{
bool flag = false;
for(int i = 2; i <= n/2; ++i)
{
if(n%i == 0)
{
flag = true;
break;
}
}
return flag;
}Thực tế để bài toán tối ưu hơn thì chúng ta sẽ không cho dòng chạy for chạy từ 2 tới n/2 mà chạy từ 2 tới căn của n như sau:
Mã:
int kiemTraSoNguyenTo(int n)
{
if (n<2) return 0;
for (i=2; i <=(int)sqrt(n); i++)
if (n%i==0) return 0;
return 1;
}Xem thêm: Bài tập C++: Viết chương trình, hàm kiểm tra số chính phương
- Chủ đề
- bai tap c so nguyen to
