#19 알고리즘 연습 - 소수찾기(에라토스테네스의 체)(Python)
2019-04-08
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를 반환
문제풀이
- n(n+1)/2이상의 복잡도
기존에 내가 알던 소수라하면 n이라는 수가 있을때 1과 n만이 약수로 있으므로
각 수마다 for문으로 나누어 떨어지는지 체크해주게 되고 그렇게 되면 2일때 2번 3일때 3번 4일때 4번이므로 n까지 가게되면 n까지의 합인 n(n+1)/2이상의 복잡도가 걸린다 - n^3/2 이상의 복잡도
그래서 보다 쉽게 소수를 구하는 방법을 검색하여 에라토스테네스의 체를 이용하여 구현하는데 이 경우에는 n^3/2 이상의 복잡도임을 알수 있다.
2중 for문이 들어가서 아무리 줄이려고 해도 기준치 이상의 시간이 걸리고 있었다. - 2* n^1/2 정도의 시간 복잡도
더이상 아무런 아이디어가 떠오르지 않아 wiki에 있는 python code 를 살짝 보니 range()의 공차를 설정하는 방법을 이용해서 간편화를 시켰다.
전혀 생각지도 못한 아이디어였는데 range()의 활용도에 대해 다시한번 느끼게 되는 계기가 되었다.
range()를 활용한 경우 2* n^1/2 정도의 시간 복잡도가 걸리는 것 같다 (오랜만에 시그마와.. 덧셈공식을 열심히 사용해서 계산해 봤다)
무식한 코드
def solution(n):
result = []
for i in range(2, n+1): #n만큼의 범위에 있는 수 반복
flag = 0 #소수인지 확인하기 위해서 flag를 for돌때마다 초기화
for j in range(1, i+1): #판단하고자하는 수까지의 약수갯수 구함
if i % j == 0: #나누어 떨어지면 flag(약수 갯수)를 증가시킴
flag += 1
if flag == 2: # 약수의 갯수가 2라면 소수 list에 추가해주자
result.append(i)
return len(result)테스트 1 〉 통과 (0.04ms, 10.7MB)
테스트 2 〉 통과 (0.64ms, 10.7MB)
테스트 3 〉 통과 (4.26ms, 10.7MB)
테스트 4 〉 통과 (18.25ms, 10.7MB)
테스트 5 〉 통과 (8.19ms, 10.7MB)
테스트 6 〉 통과 (1573.36ms, 10.7MB)
테스트 7 〉 통과 (126.92ms, 10.7MB)
테스트 8 〉 통과 (815.00ms, 10.7MB)
테스트 9 〉 통과 (2167.10ms, 10.7MB) 이처럼 생각보다 기하급수적으로 시간이걸림
테스트 10 > 실패 (시간 초과)내 첫번째 풀이 🏆
def solution(n):
temp = [] # 결과물을 담아낼 list생성
flag = int(n ** 0.5) # 이때의 flag는 '체'를 사용하는데 있어 기준이 되는 n^1/2를 나타낸다
#체의 특징중에서 n^1/2이전까지만 체크를 해주면 소수를 판별해줄수 있다.
for j in range(2, n+1):
# 2~n+1까지 숫자를 먼저 가져온것은 각 숫자별로 flag까지의 숫자들로 나뉘는지 판단하여 넣어주기 위해
for i in range(2, flag+2): #만약 flag부분을 밖으로 빼면 값이 제대로 나오지 않는다. 3의 배수가 append된다던지
if j % i == 0 and j == i:
temp.append(j) # 이것은 flag로 시작하는 2 or 3 같은 애들을 추가해주기 위해 넣어준 코드이다
break # 해당 수에 if문으로 들어와서 검사가 끝났으면 내부 for문은 더이상 수행할 필요 없다.
elif j % i == 0: # 얘는 소수들의 배수이므로 그냥 무시하자
break
if i == flag+1: #마지막까지 for문이 돌았다는것은 해당 j가 나뉘는게 없다는 뜻이고 소수라는 뜻이므로 j를 추가해준다
temp.append(j)
return len(temp)테스트 1 〉 통과 (0.05ms, 10.7MB)
테스트 2 〉 통과 (0.18ms, 10.8MB)
테스트 3 〉 통과 (0.40ms, 10.7MB)
테스트 4 〉 통과 (0.90ms, 10.7MB)
테스트 5 〉 통과 (0.58ms, 10.8MB)
테스트 6 〉 통과 (13.22ms, 10.8MB)
테스트 7 〉 통과 (2.79ms, 10.8MB)
테스트 8 〉 통과 (8.72ms, 10.8MB)
테스트 9 〉 통과 (16.64ms, 10.8MB)
테스트 10 〉 통과 (1804.97ms, 12MB)
테스트 11 〉 통과 (9465.43ms, 13.6MB) 테스트는 겨우 통과했지만 효율성 검사에서는 통과하지 못했다.
테스트 12 〉 통과 (2121.24ms, 12.1MB)내 두번째 풀이 🏆
def solution(n):
mylist =[1]*(n+1) #따로 list에 값을 append하는 것이 아니라 소수이면 1이도록 나타내는 list를 만들어 놓고
#소수가 아닌것만 0로 바꿔나가자.
flag = int(n ** 0.5) #기준이 되는 flag
for j in range(2,flag+2): #이번에는 flag들을 기준으로 하여
for i in range(0,len(mylist),j): #flag의 배수들을 소수가 아닌것으로 바꿔나가자
if i==j: #j 와 i 가 같으면 2,3 이런 소수인 애들이므로 바꾸지 않고 계속 for문을 진행
continue
mylist[i] = 0 #아니라면 다 바꿔준다 0은 소수가 아님을 나타내는 값
mylist[1] = 0 #1은 소수가 아니므로 인위적으로 0으로 대입해준다 ( 0은 내부 range에서 바뀌므로 제외)
return mylist.count(1) #1의 갯수만을 세어주면 소수의 갯수가 세어진다테스트 1 〉 통과 (0.05ms, 10.8MB)
테스트 2 〉 통과 (0.08ms, 10.8MB)
테스트 3 〉 통과 (0.12ms, 10.8MB)
테스트 4 〉 통과 (0.22ms, 10.8MB)
테스트 5 〉 통과 (0.17ms, 10.8MB)
테스트 6 〉 통과 (1.83ms, 10.8MB)
테스트 7 〉 통과 (0.51ms, 10.8MB)
테스트 8 〉 통과 (1.33ms, 10.7MB)
테스트 9 〉 통과 (2.21ms, 10.8MB)
테스트 10 〉 통과 (95.47ms, 12.6MB)
테스트 11 〉 통과 (345.38ms, 17.1MB) 속도차이가 엄청난것을 알수 있다.
테스트 12 〉 통과 (107.00ms, 12.9MB)다른 풀이 🏆
def solution(n):
num=set(range(2,n+1)) #set으로 해당 range내의 숫자들을 담아줬다.
for i in range(2,n+1): #해당 숫자까지 반복문을 돌며
if i in num: #i가 num안에 있으면(첫번째 실행결과로 2의 배수는 사라진다)
num-=set(range(2*i,n+1,i)) #차집합을 이용해서... 2*i부터 시작해 지워나간다 (2*i부터 시작하면 2,3,이런 애들이 지워질염려 없음)
return len(num)