Bài tập  /  Bài đang cần trả lời

Cho một dãy N số nguyên dương, đếm số lương số nguyên tố kép có trong dãy

Bài 11: Cho một dãy N số nguyên dương: a1, a2, a3, …, aN (N<=106,|????????| ≤ 109)
Đếm số lương số nguyên tố kép có trong dãy. Nguyên tố kép là số nguyên tố mà
tổng các chữ số của nó cũng là số nguyên tố
* Dữ liệu: cho từ tệp B11.Inp:
+ Dòng đầu chứa hai số nguyên dương N
+ Dòng tiếp theo chứa N số nguyên a1, a2, a3, …, aN
* Kết quả: ghi ra tệp B11.out số lượng đếm được
1 trả lời
Hỏi chi tiết
180
Tham khảo câu trả lời từ Trợ lý ảo Lazi
Để giải bài toán này, ta cần xây dựng một hàm kiểm tra một số có phải là số nguyên tố hay không. Sau đó, ta duyệt qua từng số trong dãy và kiểm tra xem số đó có phải là số nguyên tố kép hay không.

Dưới đây là code Python để giải bài toán:

```python
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True

def sum_of_digits(n):
return sum(int(digit) for digit in str(n))

def count_twin_primes(numbers):
count = 0
for number in numbers:
if is_prime(number) and is_prime(sum_of_digits(number)):
count += 1
return count

# Đọc dữ liệu từ file input
with open('B11.Inp', 'r') as f:
N = int(f.readline())
numbers = list(map(int, f.readline().split()))

# Tính số lượng số nguyên tố kép
result = count_twin_primes(numbers)

# Ghi kết quả vào file output
with open('B11.out', 'w') as f:
f.write(str(result))
```

Độ phức tạp của thuật toán này là O(N * sqrt(M)), trong đó N là số lượng số trong dãy và M là giá trị lớn nhất trong dãy.
0
0
Tú Quyên
23/07/2023 09:37:56
+5đ tặng

1. Đọc dữ liệu từ tệp B11.Inp:
- Đọc giá trị N từ dòng đầu tiên.
-Đọc dãy số a từ dòng tiếp theo.
2. Xây dựng hàm kiểm tra số nguyên tố:
- Nếu số đó nhỏ hơn 2, trả về False.
- Duyệt từ 2 đến căn bậc hai của số đó:
- Nếu số đó chia hết cho một số trong khoảng đó, trả về False.
- Nếu không có số nào trong khoảng đó chia hết, trả về True.
3. Khởi tạo biến đếm số lượng số nguyên tố kép là 0.
4. Duyệt qua từng số trong dãy a: - Tính tổng các chữ số của số đó.
- Kiểm tra xem tổng đó có phải là số nguyên tố hay không:
- Nếu là số nguyên tố, tăng biến đếm lên 1.
5. Ghi kết quả vào tệp B11.out.
Dưới đây là mã Python thực hiện thuật toán trên: ```python def is_prime(n): if n < 2: return False for i in range(2, int(n**0.5) + 1): if n % i == 0: return False return True with open('B11.Inp', 'r') as f_in: N = int(f_in.readline()) a = list(map(int, f_in.readline().split())) count = 0 for num in a: digit_sum = sum(map(int, str(num))) if is_prime(digit_sum): count += 1 with open('B11.out', 'w') as f_out: f_out.write(str(count)) ``` Độ phức tạp của thuật toán này là O(N * log(M)), trong đó N là số lượng số trong dãy và M là tổng số chữ số của tất cả các số trong dãy.

...

Mở khóa để xem toàn bộ nội dung trả lời

(?)
Bạn đã đạt đến giới hạn của mình. Bằng cách Đăng ký tài khoản, bạn có thể xem toàn bộ nội dung trả lời
Cải thiện điểm số của bạn bằng cách đăng ký tài khoản Lazi.
Xem toàn bộ các câu trả lời, chat trực tiếp 1:1 với đội ngũ Gia sư Lazi bằng cách Đăng nhập tài khoản ngay bây giờ
Tôi đã có tài khoản? Đăng nhập

Bạn hỏi - Lazi trả lời

Bạn muốn biết điều gì?

GỬI CÂU HỎI
Học tập không giới hạn cùng học sinh cả nước và AI, sôi động, tích cực, trải nghiệm
Bài tập Lập trình Lớp 7 mới nhất
Trắc nghiệm Lập trình Lớp 7 mới nhất

Hôm nay bạn thế nào? Hãy nhấp vào một lựa chọn, nếu may mắn bạn sẽ được tặng 50.000 xu từ Lazi

Vui Buồn Bình thường

Học ngoại ngữ với Flashcard

×
Trợ lý ảo Trợ lý ảo
×
Đấu trường tri thức | Lazi Quiz Challenge +500K