[프로그래머스] LEVEL1 소수 찾기, python3

첫번째 시도

def solution(n):
    answer = 0
    prime_num=[]
    for i in range(2,n+1):
        for j in range(2,i+1):
            if (i%j==0):
                if (i!=j):
                    break
                prime_num.append(i)
    answer = len(prime_num)
    return answer

효율이 좋지 않아서(시간초과되어서) 전체를 다 풀지 못하였다.

---

두번째 시도

def solution(n):
    answer = 0
    prime_num=[]
    for i in range(2,n+1):
        chk=True
        for j in prime_num:
            if (i%j==0):        # if i isnt primenum
                chk=False       # chk changes false
                break
        if chk:                 # chk is true
            prime_num.append(i) # add i to prime_num
    answer = len(prime_num)
    return answer

마찬가지로 정확도테스트 10,11,12 와 효율성 테스트 1,2,3,4를 풀지 못하였다. (시간초과)

 

---

세번째 시도

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

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

앞에서부터 하나씩 확인하는건 맞지만 뒤로 갈수록 비교하는게 적어져서 효율이 더 좋은 방법이다.

결과는 통과.