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):
answer = 0
DEC = [2]
for i in range(2,n+1):
for j in range(0,len(DEC)):
if i%DEC[j]==0:
break
elif j==len(DEC)-1:
DEC.append(i)
#print(DEC)
return len(DEC)
DEC
이라는 소수를 담는 list
를 만들어 가장 작은 소수 2
를 미리 넣어놓고 다음 들어오는 수가 DEC
에 있는 모든 수와 나누어봐 나머지가 없으면 DEC
에 append()
했습니다. 마지막에는 DEC
의 크기가 소수의 개수이기 때문에 len(DEC)
을 반환했습니다.
이렇게 만들어진 코드는 16개의 테스트 중 9개만 통과하고 나머지는 시간초과로 실패하였습니다. 그래서 새로운 방식으로 접근했습니다.
소수를 찾는 방식 중에 에라토스테네스의 체
라는 방식이 있습니다. 고대 수학자 에라토스테네스가 발견한 방식으로 2의 배수부터 제거하고 그 후에 제거되지않은 수는 소수이며 해당 소수의 배수를 다시 제거합니다. 이렇게 찾는게 아닌 역으로 지우는 방식으로, 아래 gif
를 보면 이해가 잘 될 것입니다.
def solution(n):
answer = 0
DEC = [True] * (n+1)
for i in range(2,n+1):
if DEC[i]==True :
for j in range(i,n+1,i):
DEC[j]=False
answer += 1
else:
continue
return answer
이를 코드로 구현한 모습입니다. 저는 먼저 입력된 정수 n
만큼 DEC
에 True
를 정의해주었습니다. 그 다음에 2
부터 n+1
까지 수 중에 True
인 값이 있으면 그 값의 배수를 모두 False
로 바꾸어주었습니다.
이 방식을 통해 남은 수는 모두 소수 이므로 True
가 발견 될때마다 answer
를 1씩 증가시켰습니다.
에라토스테네스의 체
를 전에도 사용한 기억이 있어서 해결할 수 있었지만 해당 알고리즘에 대한 지식이 없었으면 효율성 테스트에서 고생했을 것 같다.