7260 - [B]找出质数对的和等于正整数的数对

admin

给定一个正整数，编写程序找出质数对的和等于输入的这个正整数的数对，数对第一个数小于等于第二个数，并输出结果。输入值小于1000，大于5

1 n7 R( D$ A( w, w0 W) Q

1. def is_prime(num):
   , {' @0 D1 c# i5 S/ ]
2.     for i in range(2,int(num**0.5)+1):
   
3.         if num % i ==0:
   
4.             return False
   
5.     else:
   & O, ~* F7 E" a! e  u) a
6.         return True
   
7. num=int(input())
   
8. prime_ls=[int(i)for i in range(2,num) if is_prime(i)]
   ) b6 ~' a0 e) K$ Y% S; a4 M
9. #print(primelist)
   ' Q- J" A' f$ E3 n2 K5 S. G
10. 
    & w0 }4 W! {( `" Z( I5 ~" _
11. 
    ! s5 }# f! t+ `) C& [5 i# w
12. # # 方法一，循环判断
    * ?2 N" g" p; \% K7 S6 m
13. # data=[]
    
14. # for num1 in prime_ls:
    4 D8 g2 x& X. a; ~. }1 U( Y$ U
15. #     for num2 in prime_ls:
      C5 X' L/ V1 F' _/ }8 y
16. #         if num1+num2==num and num1<=num2:
    
17. #             data.append((num1,num2))
    ( J; W- N" I3 x, T$ X
18. #             data=list(set(data))
    
19. # data.sort()
    
20. # for i in data:
    
21. #     print(i[0],i[1])
    ; I/ ?7 B" P! Z' f; A
22. 
    6 q9 q) f2 `! S0 c9 I
23. # 方法二，滑动区间法
    
24. l = 0
    * e, h; y! s$ o$ R/ w* l& o
25. r = len(prime_ls)-1
    
26. data = []
    
27. while l<=r:
    $ E5 q, b% d3 V  ^1 U- v: F8 R
28.     result = prime_ls[l] + prime_ls[r]
    1 o- R4 G5 u) S' O- ^' Q) x/ r( R
29.     if result>num:
    5 `! F: j8 N- K6 r- X
30.         r-=1
    + M/ {6 S7 Q" F1 w# J1 d3 V
31.     elif result<num:
    
32.         l+=1
    
33.     else:
    
34.         # print(prime_ls[l],prime_ls[r])
    
35.         data.append([prime_ls[l],prime_ls[r]])
    
36.         l+=1
    
37. data.sort()
    & y5 [8 s3 R, T, T1 A
38. for i in data:
    
39.     print(i[0],i[1])

复制代码