Mảng 2 chiều trong Python: Vị trí số nguyên tố

Bài toán: Cho mảng hai chiều a kích thước M x N. Hãy đưa ra vị trí chứa phần tử trong mảng là số nguyên tố.

Dữ liệu: Vào từ tệp ‘ARR2DPRI.INP’ gồm:

Dòng 1: Ghi số nguyên dương M và N là kích thước mảng a (M, N ≤ 1000).
M dòng tiếp theo, dòng thứ i ghi N số nguyên dương a[i,j] (ai,j ≤ 10^6).

Kết quả: Ghi ra tệp ‘ARR2DPRI.OUT’ mỗi vị trí thoả mãn ghi trên một dòng. Nếu không có phần tử nào thoả mãn thì ghi ra -1.

Dưới đây là một đoạn mã Python để giải quyết bài toán này dựa trên yêu cầu của bạn. Bạn cần đảm bảo rằng tệp ‘ARR2DPRI.INP’ chứa dữ liệu đúng theo định dạng đã mô tả:

import math

# Hàm kiểm tra xem một số có phải là số nguyên tố hay không
def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True

# Đọc dữ liệu từ tệp 'ARR2DPRI.INP'
with open('ARR2DPRI.INP', 'r') as file:
    M, N = map(int, file.readline().split())
    a = [list(map(int, file.readline().split())) for _ in range(M)]

# Tìm vị trí của các số nguyên tố và lưu vào danh sách
prime_positions = []
for i in range(M):
    for j in range(N):
        if is_prime(a[i][j]):
            prime_positions.append((i, j))

# Ghi danh sách vị trí vào tệp 'ARR2DPRI.OUT'
with open('ARR2DPRI.OUT', 'w') as file:
    if len(prime_positions) == 0:
        file.write('-1\n')
    else:
        for position in prime_positions:
            file.write(f'{position[0]} {position[1]}\n')

Vì hàm nguyên tố bị gọi nhiều lần nên chi phí thời gian thực hiện là quá lớn. Để khắc phục điều ta sử dụng Sàng nguyên tố Eratosthenes (liệt kê các số nguyên tố từ 1 tới N với độ phức tạp thuật toán O(N)).

import math

# Hàm sàng Eratosthenes để tạo danh sách các số nguyên tố
def sieve_eratosthenes(limit):
    sieve = [True] * (limit + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(math.sqrt(limit)) + 1):
        if sieve[i]:
            for j in range(i * i, limit + 1, i):
                sieve[j] = False
    primes = [i for i, is_prime in enumerate(sieve) if is_prime]
    return primes

# Đọc dữ liệu từ tệp 'ARR2DPRI.INP'
with open('ARR2DPRI.INP', 'r') as file:
    M, N = map(int, file.readline().split())
    a = [list(map(int, file.readline().split())) for _ in range(M)]

# Tạo danh sách các số nguyên tố dưới giới hạn 10^6
primes = sieve_eratosthenes(10**6)

# Tìm vị trí của các số nguyên tố và lưu vào danh sách
prime_positions = []
for i in range(M):
    for j in range(N):
        if a[i][j] in primes:
            prime_positions.append((i, j))

# Ghi danh sách vị trí vào tệp 'ARR2DPRI.OUT'
with open('ARR2DPRI.OUT', 'w') as file:
    if len(prime_positions) == 0:
        file.write('-1\n')
    else:
        for position in prime_positions:
            file.write(f'{position[0]} {position[1]}\n')

Bạn có thể sử dụng đoạn code sau để nhập dữ liệu và xem trực tiếp trên màn hình:

import math

# Hàm kiểm tra xem một số có phải là số nguyên tố hay không
def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True

# Kích thước của mảng hai chiều
M, N = 3, 3  # Đổi giá trị M và N theo kích thước thực tế của bạn

# Mảng hai chiều
a = [
    [2, 4, 7],
    [11, 8, 13],
    [17, 19, 20]
]

# Duyệt qua từng phần tử trong mảng và kiểm tra xem có phải số nguyên tố không
prime_positions = []
for i in range(M):
    for j in range(N):
        if is_prime(a[i][j]):
            prime_positions.append((i, j))

# In ra vị trí của các số nguyên tố
for position in prime_positions:
    print(f"Số nguyên tố tại vị trí ({position[0]}, {position[1]})")

Tất nhiên, chúng ta có thể sử dụng thuật toán sàng nguyên tố để tăng tốc thực hiện và tối ưu hóa thuật toán.

import math

# Hàm sàng Eratosthenes để tạo danh sách các số nguyên tố
def sieve_eratosthenes(limit):
    sieve = [True] * (limit + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(math.sqrt(limit)) + 1):
        if sieve[i]:
            for j in range(i * i, limit + 1, i):
                sieve[j] = False
    primes = [i for i, is_prime in enumerate(sieve) if is_prime]
    return primes

# Kích thước của mảng hai chiều
M, N = map(int, input().split())  # Đọc kích thước từ input hoặc tệp nếu cần

# Mảng hai chiều a (đọc từ input hoặc tệp nếu cần)
a = []
for _ in range(M):
    row = list(map(int, input().split()))  # Đọc mỗi hàng từ input hoặc tệp nếu cần
    a.append(row)

# Tạo danh sách các số nguyên tố dưới giới hạn là số nguyên tố lớn nhất trong mảng
max_element = max(max(row) for row in a)
primes = sieve_eratosthenes(max_element)

# Tìm vị trí của các số nguyên tố và lưu vào danh sách
prime_positions = []
for i in range(M):
    for j in range(N):
        if a[i][j] in primes:
            prime_positions.append((i, j))

# In danh sách vị trí
if not prime_positions:
    print(-1)
else:
    for position in prime_positions:
        print(position[0], position[1])

Lập trình Python

Mảng 2 chiều trong Python: Vị trí số nguyên tố

Trả lời Hủy