[프로그래머스/Level1/파이썬3] 소수 찾기

코딩테스트 연습 - 소수 찾기

 

 

 

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

 

 

 

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

 

 

 

입출력 예

n	result
10	4
5	3

 

 

입출력 예 설명

- 입출력 예#1

1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

 

- 입출력 예#2

1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

 

 

 

 

나의 코드

def solution(n):
    count = 0
    for n in range(2, n+1):
        for i in range(2, n):
            if n%i == 0:
                break
        else:    
            count += 1
    return count

for 변수 in 반복가능자:    
       코드1
else:    
       코드2
 

for n in lst:    
      if n==0:
          break    
      print(n)
else:    
      print(‘There is no 0.’) # break문을 만나지 않았다면 수행된다.
 

 

이 예제의 경우 lst 안에 0이 있다면 break를 만나고 따라서  else 는 수행되지 않고 for문을 빠져 나오게 된다. 

for 문이 종료된 시점에서 이 종료가 모든 반복을 다 수행한 후의 정상적인 종료인지, 아니면 break에 의한 강제 종료인지에 따라서 수행해야 될 일을 구분할 필요가 있는 경우에 for~else 구문을 사용한다.

다른 코드

def solution(n):
    num = set(range(2,n+1))
    
    for i in range(2,n+1):
        if i in num:
            num -= set(range(2*i, n+1, i))
 
    return len(num)

 

'에라토스테네스의 체(Sieve of Eratosthenes)'라는 방법이 사용된 코드. n까지의 모든 소수를 구한다고 하면 2를 제외한 모든 2의 배수를 num에서 제거. 3을 제외한 모든 3의 배수를 num에서 제거. 4는 아까 2에서 제거. 5를 제외한 모든 5의 배수를 num에서 제거. 이렇게 반복해서 num에 남아 있는 수들이 소수이다. 대량의 소수를 한꺼번에 판별하고자 할 때 사용한다.