[python] 백준 2581 : 소수

2581번 문제는 다음과 같다.

 

 

문제 이해는 다음과 같다.

입력 숫자 두개 사이의 숫자에서 소수를 찾아,

소수의 합과 최솟값을 찾을 것이다.

 

여기서 소수란?

저번 글에서 설명했던 것과 같이 약수가 자기 자신과 1뿐인 수이다.

즉, 나누어떨어지는 수가 1과 자기 자신 뿐으로 2개이다.

 

 

입력으로 시작하는 숫자와, 마지막 숫자를 M, N순서대로 입력받기에 

int(input())

를 각각해준다.

 

나는 소수를 집어넣을 공간을 리스트로 만들어주었다.

lst = []

 

입력받은 숫자 M부터 N까지 하나씩 증가하면서, 

약수의 갯수를 찾아야하므로 약수 갯수는 0으로 초기화한다.

for i in ragnge(M, N+1):
	k = 0 # 약수 계산해주는 수이다.

 

이제 돌아가면서 약수의 갯수를 셀 것인데,

M이 만약 1이 되면 i는 1부터 돌아갈 것이다.

하지만 약수는 2부터 시작이므로

i는 1보다 클 때, 다시 나머지가 0인 수, 즉 나누어 떨어지는 수를 포문을 돌면서 약수의 갯수를 1씩 증가 시킬 것이다.

if i>1: 
  for j in range(2,i): 
    if i % j == 0: 
      k+=1 
      break 
  if k ==0:
    lst.append(i) #lst에 소수 출력

 

k가 그대로 0이면, 소수이므로 lst에 현재 숫자를 추가한다.

 

후, 최종 lst에 담긴 소수의 합과 최솟값을 출력할 것이고,

소수가 없다면 -1을 출력하는 출력문을 작성해준다.

 

if len(lst)>0:
  print(sum(lst))
  print(min(lst))
else:
  print(-1)

 

최종 코드는 다음과 같다.

 

M = int(input()) # 시작숫자
N = int(input()) #마지막숫자

lst = [] # 소수를 집어넣을 리스트
for i in range(M,N+1): #M부터 N+1까지
  k = 0 #약수 계산해주는 수 
  if i>1: #i가 M부터인데, 숫자1보다 커야함 왜냐?소수는 2부터시작
    for j in range(2,i): 
      if i % j == 0: # 나머지가 0이면
        k+=1 # 약수개수 증가
        break #1이상이면 필요없으니 이프문 밖으로나가도 상관x
    if k ==0:
      lst.append(i) #lst에 소수 출력 
  
if len(lst)>0:
  print(sum(lst))
  print(min(lst))
else:
  print(-1)