Code Số siêu nguyên tố trong đoạn bằng C++
Trước khi đi vào bài tập cụ thể, thầy ôn lại một chút về khái niệm số nguyên tố nhé.
1. Nhắc lại kiến thức về Số nguyên tố
Số nguyên tố là một số tự nhiên lớn hơn 1, chỉ có hai ước số dương phân biệt là 1 và chính nó.
Ví dụ: 2, 3, 5, 7, 11, 13, … là các số nguyên tố.
Số 1 không phải là số nguyên tố. Số 0 và các số âm cũng không xét trong định nghĩa này.
2. Phân tích yêu cầu bài toán
Đề bài yêu cầu chúng ta tìm tất cả các số siêu nguyên tố trong một đoạn cho trước.
“Số siêu nguyên tố” là một khái niệm có thể hơi lạ với các em, nhưng thực chất, trong chương trình sách giáo khoa Tin học lớp 9, chúng ta sẽ hiểu “số siêu nguyên tố” ở đây là các số nguyên tố. Có thể đề bài dùng từ “siêu nguyên tố” để nhấn mạnh tính chất đặc biệt của các số này.
Vậy, bài toán của chúng ta quy về việc:
– Cho hai số tự nhiên \(a\) và \(b\) là hai đầu mút của một đoạn.
– Tìm và đếm tất cả các số nguyên tố \(x\) sao cho \(a <= x <= b\).
3. Xây dựng thuật toán
Để giải bài toán này, chúng ta sẽ thực hiện hai bước chính:
Bước 1: Viết hàm kiểm tra một số có phải là số nguyên tố hay không.
Giả sử chúng ta có một số \(n\). Để kiểm tra \(n\) có phải là số nguyên tố hay không, ta làm như sau:
– Nếu \(n <= 1\), thì \(n\) không phải là số nguyên tố.
- Nếu \(n > 1\), ta sẽ kiểm tra xem \(n\) có chia hết cho bất kỳ số nào từ 2 cho đến căn bậc hai của \(n\) hay không.
– Tại sao lại chỉ kiểm tra đến căn bậc hai của \(n\)?
Giả sử \(n\) có một ước số \(d\) lớn hơn \(sqrt(n)\). Khi đó, \(n / d\) sẽ là một ước số khác của \(n\) và \(n / d\) sẽ nhỏ hơn \(sqrt(n)\). Điều này có nghĩa là nếu \(n\) có ước số lớn hơn \(sqrt(n)\), thì nó cũng phải có ước số nhỏ hơn \(sqrt(n)\). Do đó, chỉ cần kiểm tra các ước số từ 2 đến \(sqrt(n)\) là đủ.
– Nếu \(n\) chia hết cho bất kỳ số nào trong khoảng này, thì \(n\) không phải là số nguyên tố.
– Nếu \(n\) không chia hết cho bất kỳ số nào trong khoảng này, thì \(n\) là số nguyên tố.
Công thức tính căn bậc hai của \(n\) là \( \sqrt{n} \).
Bước 2: Duyệt qua từng số trong đoạn [a, b] và đếm các số nguyên tố.
– Chúng ta sẽ sử dụng một vòng lặp để duyệt qua tất cả các số \(i\) từ \(a\) đến \(b\).
– Với mỗi số \(i\), chúng ta gọi hàm kiểm tra số nguyên tố đã xây dựng ở Bước 1.
– Nếu hàm trả về kết quả là \(true\) (tức là \(i\) là số nguyên tố), chúng ta sẽ tăng một biến đếm lên 1.
– Sau khi kết thúc vòng lặp, biến đếm này sẽ cho chúng ta biết tổng số các số nguyên tố trong đoạn [a, b].
4. Viết chương trình bằng C++
Bây giờ, chúng ta sẽ chuyển thuật toán trên thành mã C++.
4.1. Khai báo thư viện và biến
Chúng ta cần thư viện \(iostream\) để nhập xuất và thư viện \(cmath\) để sử dụng hàm \(sqrt\).
cpp
#include
#include
int main() {
int a, b; // Biến lưu hai đầu mút của đoạn
std::cout << "Nhap hai so nguyen a va b: ";
std::cin >> a >> b;
int demSoNguyenTo = 0; // Biến đếm số lượng số nguyên tố
// … phần còn lại của chương trình sẽ được viết ở đây
return 0;
}
4.2. Viết hàm kiểm tra số nguyên tố
Chúng ta sẽ định nghĩa một hàm có tên \(laSoNguyenTo\) nhận vào một số nguyên \(n\) và trả về \(true\) nếu \(n\) là số nguyên tố, ngược lại trả về \(false\).
cpp
bool laSoNguyenTo(int n) {
if (n <= 1) {
return false; // Số nhỏ hơn hoặc bằng 1 không phải số nguyên tố
}
// Kiểm tra các ước số từ 2 đến căn bậc hai của n
for (int i = 2; i <= sqrt(n); ++i) {
if (n % i == 0) {
return false; // Nếu n chia hết cho i, thì n không phải số nguyên tố
}
}
return true; // Nếu không tìm thấy ước số nào, thì n là số nguyên tố
}
4.3. Kết hợp hàm vào hàm chính và hoàn thiện chương trình
Bây giờ, chúng ta sẽ đặt hàm \(laSoNguyenTo\) vào trong \(main\) và sử dụng vòng lặp để duyệt đoạn [a, b].
cpp
#include
#include
// Hàm kiểm tra số nguyên tố
bool laSoNguyenTo(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i <= sqrt(n); ++i) {
if (n % i == 0) {
return false;
}
}
return true;
}
int main() {
int a, b;
std::cout << "Nhap hai so nguyen a va b: ";
std::cin >> a >> b;
int demSoNguyenTo = 0;
// Duyệt qua từng số trong đoạn [a, b]
for (int i = a; i <= b; ++i) {
if (laSoNguyenTo(i)) { // Kiểm tra xem số i có phải là số nguyên tố không
demSoNguyenTo++; // Nếu là số nguyên tố thì tăng biến đếm
// Nếu muốn in ra các số siêu nguyên tố, ta có thể thêm dòng này:
// std::cout << i << " ";
}
}
// In kết quả
std::cout << "So luong so nguyen to trong doan [" << a << ", " << b << "] la: " << demSoNguyenTo << std::endl;
return 0;
}
5. Giải thích chi tiết từng dòng code
Hàm \(laSoNguyenTo(int n)\):
– \(bool laSoNguyenTo(int n)\): Định nghĩa một hàm tên là \(laSoNguyenTo\), nhận vào một tham số kiểu số nguyên \(n\), và sẽ trả về một giá trị kiểu \(bool\) (true hoặc false).
– \(if (n <= 1)\): Kiểm tra xem giá trị \(n\) có nhỏ hơn hoặc bằng 1 hay không.
- \(return false;\): Nếu \(n <= 1\), hàm trả về \(false\), báo hiệu \(n\) không phải là số nguyên tố.
- \(for (int i = 2; i <= sqrt(n); ++i)\): Vòng lặp này bắt đầu từ \(i = 2\). Nó sẽ tiếp tục chạy miễn là \(i\) còn nhỏ hơn hoặc bằng căn bậc hai của \(n\). Mỗi lần lặp, \(i\) sẽ tăng lên 1 (\(++i\)).
- \(sqrt(n)\): Hàm tính căn bậc hai của \(n\). Thư viện \(cmath\) cần được \(#include\) để sử dụng hàm này.
- \(if (n % i == 0)\): Toán tử \(%\) (modulo) trả về số dư của phép chia \(n\) cho \(i\). Nếu số dư bằng 0, nghĩa là \(n\) chia hết cho \(i\).
- \(return false;\): Nếu \(n\) chia hết cho bất kỳ \(i\) nào trong vòng lặp, \(n\) không phải là số nguyên tố, hàm trả về \(false\).
- \(return true;\): Nếu vòng lặp kết thúc mà không tìm thấy số nào \(i\) mà \(n\) chia hết, nghĩa là \(n\) chỉ chia hết cho 1 và chính nó (vì ta đã bỏ qua trường hợp \(n <= 1\)), vậy \(n\) là số nguyên tố, hàm trả về \(true\).
Hàm \(main()\):
– \(int main()\): Điểm bắt đầu của chương trình.
– \(int a, b;\): Khai báo hai biến kiểu số nguyên là \(a\) và \(b\) để lưu trữ hai đầu mút của đoạn.
– \(std::cout << "Nhap hai so nguyen a va b: ";\): Dòng này hiển thị thông báo yêu cầu người dùng nhập hai số nguyên lên màn hình. \(std::cout\) là đối tượng để xuất dữ liệu ra màn hình.
- \(std::cin >> a >> b;\): Dòng này đọc hai giá trị số nguyên mà người dùng nhập vào từ bàn phím và lưu chúng lần lượt vào biến \(a\) và \(b\). \(std::cin\) là đối tượng để nhập dữ liệu từ bàn phím.
– \(int demSoNguyenTo = 0;\): Khai báo một biến kiểu số nguyên tên là \(demSoNguyenTo\) và khởi tạo giá trị ban đầu là 0. Biến này sẽ dùng để đếm số lượng số nguyên tố tìm được.
– \(for (int i = a; i <= b; ++i)\): Vòng lặp này sẽ duyệt qua tất cả các số nguyên từ giá trị của \(a\) cho đến giá trị của \(b\). Biến \(i\) sẽ lần lượt nhận các giá trị này.
- \(if (laSoNguyenTo(i))\): Bên trong vòng lặp, chúng ta gọi hàm \(laSoNguyenTo\) với tham số là số \(i\) hiện tại. Nếu hàm trả về \(true\) (nghĩa là \(i\) là số nguyên tố)...
- \(demSoNguyenTo++;\): ...thì chúng ta sẽ tăng biến \(demSoNguyenTo\) lên 1.
- \(std::cout << "So luong so nguyen to trong doan [" << a << ", " << b << "] la: " << demSoNguyenTo << std::endl;\): Sau khi vòng lặp kết thúc, dòng này sẽ in ra màn hình kết quả cuối cùng: tổng số lượng số nguyên tố đã tìm được trong đoạn [a, b]. \(std::endl\) dùng để xuống dòng.
- \(return 0;\): Báo hiệu rằng chương trình đã kết thúc thành công.
6. Một số lưu ý thêm
– Việc sử dụng \(sqrt()\) có thể dẫn đến sai số nhỏ với các số rất lớn. Tuy nhiên, đối với phạm vi dữ liệu của lớp 9 thì cách này là hoàn toàn chấp nhận được.
– Để tối ưu hơn nữa, chúng ta có thể chỉ kiểm tra các ước số lẻ sau khi kiểm tra với số 2. Tuy nhiên, với yêu cầu của bài tập này, phương pháp trên là đủ rõ ràng và dễ hiểu.
Các em hãy thử tự mình gõ lại chương trình này và chạy thử với các cặp số khác nhau để kiểm tra nhé. Nếu có bất kỳ chỗ nào chưa hiểu, đừng ngần ngại hỏi thầy. Chúc các em học tốt!
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int m=10000000;
bool p[m+1];
void snt() {
memset(p,true,sizeof(p));
p[0]=p[1]=false;
for (int i=2;i*i<=m;++i) {
if (p[i]) {
for (int j=i*i;j<=m;j+=i) {
p[j]=false;
}
}
}
}
bool ktra(int n) {
int t=n;
while (t>0) {
if (!p[t]) {
return false;
}
t/=10;
}
return true;
}
int main() {
int a,b;
cin>>a>>b;
snt();
bool ok=false;
for (int i=a;i<=b;++i) {
if (ktra(i)) {
cout<<i<<"\n";
ok = true;
}
}
if (!ok) {
cout<<"NO";
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define ll long long
bool f[10000005];
void snt()
{
memset (f, true, sizeof(f));
f[0] = f[1] = false;
for (ll i = 2; i <= sqrt(10000000); ++i)
if (f[i]) for (ll j = i * i; j <= 10000000; j += i)
f[j] = false;
}
bool check (ll n)
{
while (n != 0)
{
if (!f[n]) return false;
n /= 10;
}
return true;
}
ll a, b, d = 0;
int main()
{
snt();
cin >> a >> b;
for (ll i = a; i <= b; ++i)
{
if (check(i))
{
cout << i << '\n';
d++;
}
}
if (d == 0) cout << "NO";
}