Đề bài
Viết chương trình C++ liệt kê tất cả số nguyên tố có 5 chữ số.
Định nghĩa: Số nguyên tố là số lớn hơn 1 và chỉ chia hết cho 1 và chính nó.
Ví dụ: 2, 3, 5, 7, 11, 13, 17, … là những số nguyên tố.
Chú ý: Số 0 và 1 không phải là số nguyên tố. Chỉ có số 2 là số nguyên tố chẵn, tất cả các số chẵn khác không phải là số nguyên tố vì chúng chia hết cho 2.
Lời giải
/**
* Chuong trinh liet ke tat ca so nguyen to co 5 chu so.
*
* @author viettuts.vn
*/
#include <iostream>
#include <cmath>
using namespace std;
/**
* check so nguyen to
*
* @author viettuts.vn
* @param n: so nguyen duong
* @return 1: la so nguyen so,
* 0: khong la so nguyen to
*/
int isPrimeNumber(int n) {
// so nguyen n < 2 khong phai la so nguyen to
if (n < 2) {
return 0;
}
// check so nguyen to khi n >= 2
int i;
int squareRoot = (int) sqrt(n);
for (i = 2; i <= squareRoot; i++) {
if (n % i == 0) {
return 0;
}
}
return 1;
}
/**
* Ham main
*/
int main() {
int count = 0;
int i;
cout << "Liet ke tat ca cac so co 5 chu so:";
for (i = 10001; i < 99999; i+=2) {
if (isPrimeNumber(i)) {
printf("%d\n", i);
count++;
}
}
printf("Tong cac so nguyen to co 5 chu so la: %d", count);
}
Kết quả:
Liet ke tat ca cac so co 5 chu so: 10007 10009 10037 ... 99971 99989 99991 Tong cac so nguyen to co 5 chu so la: 8363