Bài 2. (4,0 điểm) ĐẾM SỐ NGUYÊN TỐ Số nguyên tố là số tự nhiên lớn hơn 1, chỉ có 2 ước là 1 và chính nó. Cho dãy n số nguyên dương a1, a2,…, an , em hãy đếm xem trong dãy có bao nhiêu số nguyên tố đôi...

Bài 2. (4,0 điểm) ĐẾM SỐ NGUYÊN TỐ

Yêu cầu:

• Đếm số lượng số nguyên tố đôi một khác nhau trong dãy.

✅ Thuật toán giải Bài 2:

1. Đọc vào n và dãy a1, a2, ..., an.
2. Sử dụng sàng Eratosthenes để đánh dấu số nguyên tố tới 10^7.
3. Duyệt qua từng số ai:
   • Nếu là số nguyên tố, thêm vào tập hợp set_prime để loại trùng.
4. In ra kích thước của set_prime.

✅ Code Python cho Bài 2:

def sieve(limit):
    prime = [True] * (limit + 1)
    prime[0] = prime[1] = False
    for i in range(2, int(limit ** 0.5) + 1):
        if prime[i]:
            for j in range(i * i, limit + 1, i):
                prime[j] = False
    return prime

# Đọc file input
with open('BAI2.INP', 'r') as f:
    n = int(f.readline())
    arr = list(map(int, f.readline().split()))

# Sàng nguyên tố
is_prime = sieve(10**7)

# Tập hợp chứa các số nguyên tố duy nhất
prime_set = set()

for num in arr:
    if is_prime[num]:
        prime_set.add(num)

# Ghi file output
with open('BAI2.OUT', 'w') as f:
    f.write(str(len(prime_set)))

✅ Giải thích ví dụ:

Ví dụ 1:

Input:
5
1 3 25 19 8

Các số nguyên tố là: 3, 19
=> Có 2 số nguyên tố khác nhau.

Output: 2

Bài 4. (2,0 điểm) BIẾN ĐỔI DÃY

Yêu cầu:

• Biến đổi tất cả các phần tử trong dãy thành bằng nhau bằng cách tăng thêm X đơn vị.
• Nếu không thể, in ra -1.

✅ Thuật toán giải Bài 4:

1. Đọc vào N, X và dãy A.
2. Tìm giá trị lớn nhất maxA trong dãy.
3. Với mỗi phần tử ai:
   • Kiểm tra (maxA - ai) % X == 0.
     Nếu không chia hết, thì không thể biến đổi → in -1.
4. Tính tổng số thao tác cần làm:
   sum((maxA - ai) // X) với mọi ai.
5. In ra tổng số thao tác.

✅ Code Python cho Bài 4:

# Đọc file input
with open('BAI4.INP', 'r') as f:
    N, X = map(int, f.readline().split())
    A = list(map(int, f.readline().split()))

maxA = max(A)
count = 0
possible = True

for ai in A:
    if (maxA - ai) % X != 0:
        possible = False
        break
    count += (maxA - ai) // X

# Ghi file output
with open('BAI4.OUT', 'w') as f:
    if possible:
        f.write(str(count))
    else:
        f.write('-1')

✅ Giải thích ví dụ:

Ví dụ 1:

Input:
5 2
5 1 3 3 5

- maxA = 5
- Các chênh lệch: 0, 4, 2, 2, 0
- Kiểm tra chia hết X=2 → ok
- Tổng số bước: 0 + 2 + 1 + 1 + 0 = 4

Output: 4

Ví dụ 2:

Input:
2 100
1 10

- maxA = 10
- (10 - 1) = 9, 9 % 100 != 0 → không thể biến đổi

Output: -1