프로그래머스 - 소수찾기

< 첫 단계 작성한 코드 >

def solution(n):
    answer = 0
    for i in range(n):
      test = i+1
      chk = 0
      cnk = 0
      for x in range(test):
        test02 = x+1
        if(test%test02==0):
          chk = chk+1
        
        if(test02 != test):
          cnk = 1
          if(chk==2): break;

        if(chk == 2):
          cnk = 2  
      if(cnk==2):
        answer+=1
    return answer

 

딱 봐도 효율은 별로지만 정답으로 처리 될줄 알았다...

 

하지만 시간 초과로 계속 코드를 수정해도 해결이 안되었다..

 

어떤 함수를 사용해야 문제가 풀리는건가 ...? 싶어서 검색해보니...

 

 

에라토스테네스의 체

를 사용하라는 글들이 많았다.

 

< 내가 사용한 코드 >

def solution(n): 
    answer = 0 
    prime_num=[] 
    chk=[False]*2+[True]*(n-1)    # initialize chk, chk[0],chk[1] is not prime number
    for i in range(2,n+1): 
        if chk[i]:         # if chk[i] is 
            prime_num.append(i)
            for j in range(2*i,n+1,i): 
                if chk[j]:          # chk is True
                    chk[j]=False    # chk changes false 
    answer = len(prime_num) 
    return answer

 

 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED   %86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

 

< 추천 코드 >

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)

 

코드 이해하기

if 지정 숫자 == 120

1. 2 ~ 지정(120) 까지 num SET을 만든다.

2. 2 ~ 지정(120) 까지 반복문들 돌린다.

3. i는 계속 반복하면서 in num 으로 num 집합에 i 가 있으면 num 과 num의 배수를 모두 지움.