Tác giả:
- Trần Hán Huy – tranhanhuy.wordpress.com
Sách:
- Bài tập kĩ thuật lập trình C/C++ – Nguyễn Tấn Trần Minh Khang
Đề bài
- 144 Tìm số nguyên tố đầu tiên trong mảng 1 chiều các số nguyên. Nếu mảng không có số nguyên tố thì trả về giá trị -1
Code
int SNT(int n) { if (n<2) return 0; for (int i=2; i<n; i++) if (n%i==0) return 0; return 1; } int SNTDauTien(int a[], int n) { for(int i=0; i<n; i++) if(SNT(a[i])==1) return a[i]; return -1; }
Ở bài này, chúng ta sẽ cùng nhau ôn luyện làm bài và phân tích chi tiết cách giải quyết các bài toán trong lập trình qua ví dụ cụ thể.
Bài 1
Kiểm tra số n có phải số nguyên tố hay không.
Khái niệm số nguyên tố
Số nguyên tố là số nguyên dương có duy nhất 2 ước phân biệt là 1 và chính nó. Lưu ý: Số 1 không phải số nguyên tố do chỉ có 1 ước.
Ý tưởng kiểm tra số nguyên tố
- Nếu n < 2, kết luận n không phải số nguyên tố. Sử dụng if để kiểm tra n.
- Đếm số ước của n trong đoạn từ `
include <stdio.h>
int main() { // Add your code in here: // Fixed Do not edit anything here. printf("\nOUTPUT:\n"); // Write your output here: return 0; } 1 đến căn bậc hai của `n` (sử dụng
include <stdio.h>
int main() { // Add your code in here: // Fixed Do not edit anything here. printf("\nOUTPUT:\n"); // Write your output here: return 0; } 3). Nếu `n` không có ước nào trong đoạn từ
include <stdio.h>
int main() { // Add your code in here: // Fixed Do not edit anything here. printf("\nOUTPUT:\n"); // Write your output here: return 0; } 1 đến căn bậc hai của `n` thì nó là số nguyên tố (sử dụng `if` để kiểm tra). Ngược lại thì không phải. ### Tại sao lại chỉ đếm các ước trong đoạn từ
include <stdio.h>
int main() {// Add your code in here: // Fixed Do not edit anything here. printf("\nOUTPUT:\n"); // Write your output here: return 0; } 1 đến căn của `n`? Nếu bạn để ý thì một số nguyên
include <stdio.h>
int main() {// Add your code in here: // Fixed Do not edit anything here. printf("\nOUTPUT:\n"); // Write your output here: return 0; } 0 bất kỳ sẽ luôn có số ước ở nửa đầu căn bậc 2 của nó bằng số ước ở nửa sau căn bậc 2 của nó. Cụ thể, các ước sẽ phân bố thành 2 miền từ
include <stdio.h>
int main() {// Add your code in here: // Fixed Do not edit anything here. printf("\nOUTPUT:\n"); // Write your output here: return 0; } 1 và từ
include <stdio.h>
int main() {// Add your code in here: // Fixed Do not edit anything here. printf("\nOUTPUT:\n"); // Write your output here: return 0; } 2. Phân tích cụ thể:
Với số 12, ta có # include <stdio.h> int main() { // Add your code in here: // Fixed Do not edit anything here. printf("\nOUTPUT:\n"); // Write your output here: return 0; } 3 Đoạn \[ 2 → 3.464 \] có ước bằng 2, tương ứng đoạn \[ 3.464 → 12 \] có ước bằng 6. Đoạn \[ 2 → 3.464 \] có ước bằng 3, tương ứng đoạn \[ 3.464 → 12 \] có ước bằng 4. Trong đoạn \[ 2 → 3.464 \] số 12 chia hết cho 2 số \[ 2, 3 \] → 12 không phải là số nguyên tố.
Với số 9, ta có # include <stdio.h> int main() { // Add your code in here: // Fixed Do not edit anything here. printf("\nOUTPUT:\n"); // Write your output here: return 0; } 4 Đoạn \[ 2 → 3 \] có ước 3, tương ứng đoạn \[ 3 → 9 \] có ước 3. Trong đoạn \[ 2 → 3 \] số 9 chia hết cho 1 số \[ 3 \] → 9 không phải là số nguyên tố.
Với số 7, ta có # include <stdio.h> int main() { // Add your code in here: // Fixed Do not edit anything here. printf("\nOUTPUT:\n"); // Write your output here: return 0; } 5 Trong đoạn từ \[ 2 → 2.646 \] không có số nguyên nào mà 7 chia hết → 7 là số nguyên tố.### Triển khai code Qua phân tích bên trên chúng ta có thể nhận thấy chương trình này cần kết hợp nhiều thứ đã học lại từ trước đến này bao gồm:
- Thư viện `
- if để kiểm tra một số điều kiện.
- `
include <stdio.h>
int main() { // Add your code in here: // Fixed Do not edit anything here. printf("\nOUTPUT:\n"); // Write your output here: return 0; } 3 dùng để duyệt từ
include <stdio.h>
int main() { // Add your code in here: // Fixed Do not edit anything here. printf("\nOUTPUT:\n"); // Write your output here: return 0; } 1 đến `n` để đếm số ước của `n`. Code hoàn chỉnh: 1
include <stdio.h>
2
include <math.h>
3 4 int main() { 5 6 int n; 7 8 printf("Enter n: "); 9 scanf("%d", &n); 10 11 if (n < 2) { 12 printf("n is not a prime number.\n"); 13 return 0; 14 } 15 16 int check = 1; 17 for (int i = 2; i <= sqrt(n); i++) { 18 if (n % i == 0) { 19 printf("n is not a prime number.\n"); 20 check = 0; 21 break; 22 } 23 } 24 25 if (check) { 26 printf("n a prime number.\n"); 27 } 28 } Kết quả Enter n: 1 n is not a prime number. Kết quả Enter n: 11 n a prime number. Kết quả Enter n: 12 n is not a prime number.
include <stdio.h>
int main() {// Add your code in here: // Fixed Do not edit anything here. printf("\nOUTPUT:\n"); // Write your output here: return 0; } 3 - đây là từ khóa dùng để kết thúc một hàm xử lý, khi gặp từ khóa
include <stdio.h>
int main() {// Add your code in here: // Fixed Do not edit anything here. printf("\nOUTPUT:\n"); // Write your output here: return 0; } 3 thì chương trình sẽ không chạy tiếp các dòng mã bên dưới từ
include <stdio.h>
int main() {// Add your code in here: // Fixed Do not edit anything here. printf("\nOUTPUT:\n"); // Write your output here: return 0; } 3 nữa. Trong ví dụ trên, khi nhập `n < 2` thì chương trình sẽ chạy vào câu lệnh `if` (line 11) và thực hiện lệnh
include <stdio.h>
int main() {// Add your code in here: // Fixed Do not edit anything here. printf("\nOUTPUT:\n"); // Write your output here: return 0; } 8 (line 13) - lúc này chương trình sẽ kết thúc và những dòng mã từ line 15 → line 27 sẽ không được thực hiện.
include <stdio.h>
int main() {// Add your code in here: // Fixed Do not edit anything here. printf("\nOUTPUT:\n"); // Write your output here: return 0; } 9 - tại sao lại dùng
include <stdio.h>
int main() {// Add your code in here: // Fixed Do not edit anything here. printf("\nOUTPUT:\n"); // Write your output here: return 0; } 9 tại đây? Vì trong khoảng từ
include <stdio.h>
int main() {// Add your code in here: // Fixed Do not edit anything here. printf("\nOUTPUT:\n"); // Write your output here: return 0; } 1 có thể có rất nhiều ước của `n`, chúng ra chỉ cần tìm thấy 1 ước đầu tiên là kết luận được `n`3 mà không cần chạy hết vòng lặp (dư thừa không cần thiết). Bạn có thể đọc lại về
include <stdio.h>
int main() {// Add your code in here: // Fixed Do not edit anything here. printf("\nOUTPUT:\n"); // Write your output here: return 0; } `
9 tại đây.
Bài tập tự luyện tập
Bài 1
Nhập một số nguyên n từ bàn phím. Tính tổng tất cả các n`9 trong khoảng từ 0 cho đến bằng số nguyên `n.