#22 알고리즘 연습 소수찾기(에라토스테네스의 체) PYTHON

소수 찾기

문제 설명

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를 반환

---

---

문제풀이 IDEA

1.  n(n+1)/2이상의 복잡도

기존에 내가 알던 소수라하면 n이라는 수가 있을때 1과 n만이 약수로 있으므로

각 수마다 for문으로 나누어 떨어지는지 체크해주게 되고 그렇게 되면
2일때 2번 3일때 3번 4일때 4번이므로 n까지 가게되면 n까지의 합인 n(n+1)/2이상의 복잡도가 걸린다

2. n^3/2 이상의 복잡도

그래서 보다 쉽게 소수를 구하는 방법을 검색하여
에라토스테네스의 체를 이용하여 구현하는데 이 경우에는 n^3/2 이상의 복잡도임을 알수 있다.

2중 for문이 들어가서 아무리 줄이려고 해도 기준치 이상의 시간이 걸리고 있었다.


3. 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)

두번째 코드

1 2 3 4 5 6 7 8 9 10 11

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의 갯수만을 세어주면 소수의 갯수가 세어진다 특정 수가 소수인지 판별하는 코드 추가하기 def solution(n): mylist = [1]*(n+1) flag = int(n ** 0.5) for j in range(2, flag+2): for i in range(0, len(mylist), j): if i == j: continue mylist[i] = 0 mylist[1] = 0 if mylist[n] == 1: print(str(n) + "은 소수입니다") else: print(str(n)+"은 소수가 아닙니다") return 1 solution(int(input())) #33

테스트 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)

다른 사람의 코드

1 2 3 4 5 6 7 8

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)

-출처 : 프로그래머스