Giả sử chúng ta có một số n. Chúng ta phải kiểm tra xem n có phải là số Euclid hay không. Như chúng ta biết số Euclid là số nguyên có thể được biểu diễn dưới dạng
n =P n +1
tích của n số nguyên tố đầu tiên ở đâu.
Vì vậy, nếu đầu vào là n =211, thì đầu ra sẽ là True n có thể được biểu diễn là
211 =(2 × 3 × 5 × 7) +1
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- MAX:=10000
- số nguyên tố:=một danh sách mới
- Xác định một hàm create_all_primes (). Điều này sẽ mất
- prime:=một danh sách có kích thước MAX và điền bằng True
- x:=2
- trong khi x * x
- nếu số nguyên tố [x] là True, thì
- đối với tôi trong phạm vi x * 2 đến MAX, cập nhật từng bước x, thực hiện
- prime [i]:=False
- x:=x + 1
- nếu số nguyên tố [x] là True, thì
- nếu số nguyên tố [x] là true, thì
- chèn x vào cuối các số nguyên tố
- trả về True
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Mã mẫu
MAX = 10000 primes = [] def generate_all_primes(): prime = [True] * MAX x = 2 while x * x < MAX : if prime[x] == True: for i in range(x * 2, MAX, x): prime[i] = False x += 1 for x in range(2, MAX): if prime[x]: primes.append(x) def solve(n): generate_all_primes() mul = 1 i = 0 while mul < n : mul = mul * primes[i] if mul + 1 == n: return True i += 1 return False n = 211 print(solve(n))
Đầu vào
211
Đầu ra
True