50 Học Python – Tính trung bình các số nguyên tố trong mảng
Bài 50: In ra các số nguyên tố trong mảng và tính tổng của chúng bằng Python
Giới Thiệu
Trong bài viết này, chúng ta sẽ viết chương trình Python để tìm các số nguyên tố trong một mảng và tính tổng của chúng. Số nguyên tố là số lớn hơn 1 và chỉ chia hết cho 1 và chính nó.
Khuyến mãi lớn thêm danh sách 10 bài tập python rèn luyện kỹ năng và nâng cao tay nghề:
- Bài 51 : Tính trung bình các số nguyên tố trong mảng bằng Python
- Bài 52: Tìm số âm lớn nhất trong mảng bằng Python
- Bài 53: Tìm số nguyên lớn nhì trong mảng bằng Python
- Bài 54: Tìm số nguyên nhỏ thứ 3 trong mảng bằng Python
- Bài 55: Đếm số lượng số nguyên khác nhau trong mảng bằng Python
- Bài 56: Đếm số lần xuất hiện của từng số trong mảng bằng Python
- Bài 57: Tìm số nguyên xuất hiện nhiều lần nhất trong mảng bằng Python
- Bài 58 Tính trung bình cộng các số chính phương trong mảng bằng Python
- Bài 59: In ra câu “Chao HoTen” bằng Python
- Bài 60: Viết xâu theo thứ tự ngược lại bằng Python
Cách Xác Định Số Nguyên Tố
Một số là nguyên tố nếu:
- Lớn hơn 1.
- Không chia hết cho bất kỳ số nào khác ngoài 1 và chính nó.
Chúng ta sẽ sử dụng hai cách để kiểm tra số nguyên tố:
- Cách cơ bản sử dụng vòng lặp kiểm tra từng số.
- Cách tối ưu hóa sử dụng thuật toán Sàng Eratosthenes.
Chương Trình Python
Cách 1: Kiểm tra từng số (Cách cơ bản)
# Hàm kiểm tra số nguyên tố (Cách cơ bản)
def la_so_nguyen_to(so):
if so < 2:
return False
for i in range(2, int(so**0.5) + 1):
if so % i == 0:
return False
return True
# Hàm tìm các số nguyên tố trong mảng và tính tổng
def tim_va_tinh_tong_so_nguyen_to(mang):
danh_sach_nguyen_to = [so for so in mang if la_so_nguyen_to(so)]
tong = sum(danh_sach_nguyen_to)
return danh_sach_nguyen_to, tong
# Nhập số lượng phần tử của mảng
n = int(input("Nhập số phần tử của mảng: "))
mang = [int(input(f"Nhập phần tử thứ {i+1}: ")) for i in range(n)]
# Tìm và tính tổng số nguyên tố
danh_sach_nguyen_to, tong = tim_va_tinh_tong_so_nguyen_to(mang)
print("Các số nguyên tố trong mảng:", danh_sach_nguyen_to)
print("Tổng các số nguyên tố trong mảng:", tong)
Cách 2: Tối ưu hóa với thuật toán Sàng Eratosthenes
# Hàm Sàng Eratosthenes để tìm số nguyên tố nhanh hơn
def sang_eratosthenes(gioi_han):
la_so_nguyen_to = [True] * (gioi_han + 1)
la_so_nguyen_to[0], la_so_nguyen_to[1] = False, False
for i in range(2, int(gioi_han**0.5) + 1):
if la_so_nguyen_to[i]:
for j in range(i * i, gioi_han + 1, i):
la_so_nguyen_to[j] = False
return {x for x in range(gioi_han + 1) if la_so_nguyen_to[x]}
# Hàm tìm số nguyên tố và tính tổng sử dụng Sàng Eratosthenes
def tim_va_tinh_tong_so_nguyen_to_toi_uu(mang):
if not mang:
return [], 0
gioi_han = max(mang)
tap_nguyen_to = sang_eratosthenes(gioi_han)
danh_sach_nguyen_to = [so for so in mang if so in tap_nguyen_to]
tong = sum(danh_sach_nguyen_to)
return danh_sach_nguyen_to, tong
# Nhập số lượng phần tử của mảng
n = int(input("Nhập số phần tử của mảng: "))
mang = [int(input(f"Nhập phần tử thứ {i+1}: ")) for i in range(n)]
# Tìm và tính tổng số nguyên tố
danh_sach_nguyen_to, tong = tim_va_tinh_tong_so_nguyen_to_toi_uu(mang)
print("Các số nguyên tố trong mảng:", danh_sach_nguyen_to)
print("Tổng các số nguyên tố trong mảng:", tong)
So Sánh Hai Cách
| Phương pháp | Độ phức tạp | Ưu điểm | Nhược điểm |
| Kiểm tra từng số | O(n√m) | Dễ hiểu, dễ triển khai | Chậm khi mảng có số lớn |
| Sàng Eratosthenes | O(m log log m) | Tốc độ nhanh hơn với nhiều số | Tốn bộ nhớ hơn |
Trong đó:
- n là số lượng phần tử trong mảng.
- m là số lớn nhất trong mảng.
Ví Dụ Chạy Chương Trình
Nhập số phần tử của mảng: 6
Nhập phần tử thứ 1: 3
Nhập phần tử thứ 2: 7
Nhập phần tử thứ 3: 10
Nhập phần tử thứ 4: 13
Nhập phần tử thứ 5: 17
Nhập phần tử thứ 6: 20
Các số nguyên tố trong mảng: [3, 7, 13, 17]
Tổng các số nguyên tố trong mảng: 40
Kết Luận
Bài viết đã hướng dẫn cách tìm số nguyên tố trong mảng và tính tổng của chúng bằng hai cách:
- Cách cơ bản: Kiểm tra từng số, phù hợp với mảng nhỏ.
- Cách tối ưu hóa: Sử dụng Sàng Eratosthenes, nhanh hơn khi mảng chứa số lớn.
Hy vọng bài viết hữu ích cho bạn!
Nếu bạn thấy hay ! xin bạn 1 phút ! vui lòng đánh giá 5 sao cho trang website của chúng tôi ! để có động lực làm thêm nhiều bài hay nữa ! cảm ơn quý khách nhé !
Khóa học Python online từ cơ bản đến nâng cao
