Bài toán: Số n là Strong Prime nếu: (1) n là số nguyên tố, (2) n > trung bình cộng của số nguyên tố gần nhất trước và sau nó.
Ví dụ
n = 37: Số nguyên tố trước = 31, sau = 41. Trung bình = (31+41)/2 = 36. Vì 37 > 36 → Strong Prime.
Triển khai Python
def isPrime(num):
if num > 1:
for i in range(2, num):
if num % i == 0:
return False
return True
return False
def solve(num):
if not isPrime(num) or num == 2:
return False
last = num - 1
nxt = num + 1
while not isPrime(nxt):
nxt += 1
while not isPrime(last):
last -= 1
avg = (last + nxt) / 2
return num > avg
# Test
print(solve(37)) # True
print(solve(11)) # False: prev=7, next=13, avg=10, 11>10 → True? Wait 11 is strong prime
print(solve(13)) # False: prev=11, next=17, avg=14, 13<14
Kết quả
True
Giải thích
- Kiểm tra nguyên tố đơn giản O(n), có thể tối ưu đến O(√n).
- Tìm prime trước/sau bằng vòng lặp tăng/giảm 1.
- Số 2 loại trừ vì không có prime trước đó.
- Các strong prime đầu tiên: 11, 17, 29, 37, 41, 59, 67, 71, 79, 97...