Liệt kê tất cả các số nguyên tố nhỏ hơn n trong Python và C++
Bài viết này chúng ta cùng tìm hiểu các cách Liệt kê tất cả các số nguyên tố nhỏ hơn n trong Python và C++
Thuật toán liệt kê tất cả các số nguyên tố nhỏ hơn một số nguyên dương n
- Khởi tạo một danh sách rỗng để lưu các số nguyên tố (gọi là
prime_numbers). - Bắt đầu từ 2 (số nguyên tố đầu tiên) và lặp qua tất cả các số từ 2 đến n – 1 (vì ta muốn tìm các số nguyên tố nhỏ hơn n).
- Đối với mỗi số nguyên dương trong khoảng từ 2 đến n – 1, kiểm tra xem nó có phải là số nguyên tố hay không.
- Để kiểm tra xem một số
xcó phải là số nguyên tố, ta thực hiện các bước sau: a. Nếuxnhỏ hơn hoặc bằng 1, thì không phải là số nguyên tố. b. Nếuxlà 2 hoặc 3, thì là số nguyên tố. c. Nếuxchia hết cho 2 hoặc 3, thì không phải là số nguyên tố. d. Bắt đầu từ 5, kiểm tra xemxchia hết cho các số từ 5 đến căn bậc hai củax. Nếuxchia hết cho một trong các số này, thì không phải là số nguyên tố. e. Nếuxkhông chia hết cho bất kỳ số nào trong các số từ 5 đến căn bậc hai củax, thìxlà số nguyên tố. - Nếu số đang được kiểm tra trong bước 3 là số nguyên tố, thêm nó vào danh sách
prime_numbers. - Khi đã kiểm tra qua tất cả các số từ 2 đến n – 1, danh sách
prime_numberssẽ chứa tất cả các số nguyên tố nhỏ hơn n. - In danh sách
prime_numbersđể hiển thị các số nguyên tố.
Đây là cách thuật toán hoạt động. Nó kiểm tra từng số trong khoảng đã cho và thêm các số nguyên tố vào danh sách prime_numbers. Sau khi lặp qua tất cả các số, bạn có danh sách các số nguyên tố nhỏ hơn n.
Liệt kê tất cả các số nguyên tố nhỏ hơn n trong Python
Cách 1: Dùng chương trình kiểm tra số nguyên tố
def is_prime(num):
if num <= 1:
return False
if num <= 3:
return True
if num % 2 == 0 or num % 3 == 0:
return False
i = 5
while i * i <= num:
if num % i == 0 or num % (i + 2) == 0:
return False
i += 6
return True
def list_primes_less_than_n(n):
prime_list = []
for i in range(2, n):
if is_prime(i):
prime_list.append(i)
return prime_list
n = int(input("Nhập n: "))
prime_numbers = list_primes_less_than_n(n)
print("Các số nguyên tố nhỏ hơn", n, "là:", prime_numbers)
Trong đoạn mã trên, is_prime là một hàm kiểm tra xem một số có phải là số nguyên tố hay không, và list_primes_less_than_n là hàm liệt kê tất cả các số nguyên tố nhỏ hơn n. Sau đó, bạn nhập giá trị n từ bàn phím và chương trình sẽ in ra danh sách các số nguyên tố nhỏ hơn n.
Cách 2: Dùng Sàng Eratosthenes
def sieve_eratosthenes(n):
is_prime = [True]
* (n + 1)
is_prime[0] = is_prime[1]
= False
for p in range(2, int(n**0.5) + 1):
if is_prime[p]
:
for i in range(p * p, n + 1, p):
is_prime[i]
= False
prime_numbers = [i for i in range(2, n + 1) if is_prime[i]
]
return prime_numbers
n = int(input("Nhập n: "))
prime_numbers = sieve_eratosthenes(n)
print("Các số nguyên tố nhỏ hơn", n, "là:", prime_numbers)
Liệt kê tất cả các số nguyên tố nhỏ hơn n trong C++
#include <iostream>
#include <vector>
using namespace std;
bool isPrime(int num) {
if (num <= 1) {
return false;
}
if (num <= 3) {
return true;
}
if (num % 2 == 0 || num % 3 == 0) {
return false;
}
for (int i = 5; i * i <= num; i += 6) {
if (num % i == 0 || num % (i + 2) == 0) {
return false;
}
}
return true;
}
vector<int> listPrimesLessThanN(int n) {
vector<int> primeList;
for (int i = 2; i < n; ++i) {
if (isPrime(i)) {
primeList.push_back(i);
}
}
return primeList;
}
int main() {
int n;
cout << "Nhap n: ";
cin >> n;
vector<int> primeNumbers = listPrimesLessThanN(n);
cout << "Cac so nguyen to nho hon " << n << " la:";
for (int prime : primeNumbers) {
cout << " " << prime;
}
cout << endl;
return 0;
}
