Nguyên tố Again
Xem PDF
Điểm:
200
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
In ra tất cả cặp số nguyên tố \(A,B(A\le B)\) thỏa mãn \(A+B\) cũng là số nguyên tố và \(A+B\le N\). (In theo thứ tự từ điển từ bé đến lớn)
Input
- Dòng thứ nhất chứa số nguyên dương \(N(1\le N\le 10^6)\)
Output
-
Dòng thứ nhất in ra số \(k\) - số lượng cặp \((A,B)\) thỏa mãn yêu cầu bài toán
-
In ra \(k\) cặp \((A,B)\) thỏa mãn yêu cầu bài toán (theo thứ tự từ điển từ bé đến lớn).
Scoring
-
Subtask \(1\) (\(20\%\) số điểm): \(0<N\le 10\)
-
Subtask \(2\) (\(20\%\) số điểm): \(0<N\le 10^4\)
-
Subtask \(3\) (\(60\%\) số điểm): \(\text{Còn lại}\)
Example
Test 1
Input
7Output
2
2 3
2 5
Bình luận
def NT(n):
if n < 2:
return False
for i in range(2, int(n0.5) + 1):
if n % i == 0:
return False
return True
def sangnguyento(n):
NT=[True] * (n+1)
NT[0] = NT[1] = False
for p in range(2 , int(n0.5) +1 ):
if NT[p]==True:
for i in range( p * p , n+1 , p):
NT[i] = False
KQ= [i for i in range(n+1) if NT[i]==True]
return KQ
ds=[]
n=int(input())
cs=0
ds=[]
A=2
for i in sangnguyento(n):
B=i-2
if NT(B)==True and NT(A+B)==True:
ds.append(i)
cs+=1
print(cs)
for i in ds:
print(2,i-2)
Đề bài không rõ ràng
Sửa lại đề bài:
Nhập vào 1 số n, in ra tất cả các cặp A,B sao cho A, B và A+B đều là số nguyên tố (A+B<=n)