Hướng dẫn giải của LIST09: Các số nguyên tố
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cho dãy ~n~ số nguyên. Hãy đếm số lượng các số nguyên tố trong dãy và in chúng ra theo thứ tự giảm dần.
Cách làm
Với mỗi số, kiểm tra xem nó có phải số nguyên tố không. Nếu có thì lưu lại. Cuối cùng sắp xếp các số đã lưu giảm dần.
- Bước 1: Số nhỏ hơn 2 không phải số nguyên tố.
- Bước 2: Với số ~x \ge 2~, thử chia cho các số ~d~ từ 2 đến khi ~d \times d > x~. Nếu có ~d~ chia hết ~x~ thì ~x~ không phải số nguyên tố.
- Bước 3: Lưu các số nguyên tố vào mảng ~b~ và đếm ~m~.
- Bước 4: Sắp xếp ~b~ giảm dần bằng hai vòng
forlồng nhau, rồi in ~m~ và các số trong ~b~.
Bẫy: nếu một số xuất hiện nhiều lần trong dãy và là số nguyên tố thì được tính và in mỗi lần.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int a[1005];
// b chứa các số nguyên tố, m là số lượng
int b[1005];
int m = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
int x = a[i];
// Số nguyên tố phải lớn hơn hoặc bằng 2
int la_snt = 1;
if (x < 2) {
la_snt = 0;
}
// Thử chia cho các số d từ 2 đến căn của x, nếu chia hết thì không phải số nguyên tố
for (int d = 2; d * d <= x; d++) {
if (x % d == 0) {
la_snt = 0;
}
}
if (la_snt == 1) {
b[m] = x;
m++;
}
}
// Sắp xếp các số nguyên tố giảm dần
for (int i = 0; i < m; i++) {
for (int j = i + 1; j < m; j++) {
if (b[i] < b[j]) {
int tam = b[i];
b[i] = b[j];
b[j] = tam;
}
}
}
cout << m << "\n";
for (int i = 0; i < m; i++) {
cout << b[i] << " ";
}
cout << "\n";
return 0;
}
Bình luận