Kiểm tra số nhỏ nhất từ các chữ số cho trước có hai chữ số đầu cuối tạo thành số nguyên tố trong Python

Cho mảng digits chứa các chữ số. Tạo số nhỏ nhất có thể từ các chữ số đó (sắp xếp tăng dần). Sau đó lấy chữ số đầu và chữ số cuối để tạo thành hai số (thứ tự đầu-cuối và cuối-đầu). Kiểm tra xem hai số đó có phải số nguyên tố không.

Ví dụ: [5,2,1,7] → số nhỏ nhất 1257. Hai số tạo thành: 17 và 71, cả hai đều nguyên tố → trả về (1257, 17, 71).

Giải thuật

• Đếm tần suất chữ số, xây dựng chuỗi số theo thứ tự tăng dần.
• Tạo num từ chữ số đầu và cuối, rev từ chữ số cuối và đầu.
• Kiểm tra nguyên tố cho num và rev, trả về kết quả phù hợp.

Mã ví dụ

from collections import defaultdict

def isPrime(num):
    if num > 1:
        for i in range(2, num):
            if num % i == 0:
                return False
        return True
    return False

def solve(arr):
    digits_freq = defaultdict(int)
    for i in range(len(arr)):
        digits_freq[arr[i]] += 1
    number = ""
    for i in range(0, 10):
        for j in range(digits_freq[i]):
            number += str(i)
    num = int(number[0] + number[-1])
    rev = int(number[-1] + number[0])
    if isPrime(num) and isPrime(rev):
        return int(number), num, rev
    elif isPrime(num):
        return number, num
    elif isPrime(rev):
        return number, rev
    else:
        return False

digits = [5,2,1,7]
print(solve(digits))

Đầu vào

[5,2,1,7]

Đầu ra

(1257, 17, 71)