[프로그래머스] 소수찾기 python

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

 

 

첫 번째 푼 solution

 

 

def solution(n):
    cnt=0
    for x in range(1,n+1):
        if len([ x for i in range(1,x+1) if x%i==0 ])==2:
            cnt+=1
    return cnt

 

흐음... 시간초과가 뜨길래 나름 리스트 컴프리헨션으로 풀었는데 효과가 없었다... ㅠㅠ

 

 

 

https://coding-of-today.tistory.com/169

파이썬(Python) - 소수 찾기 알고리즘 구현하기(Prime Number)

위 블로그를 통해서 해결책을 알아낼 수 있었다. 

 

 

자연수의 약수를 구할 때는 자기자신의 제곱근까지만 확인해보면 된다는 것이다.

 

굳이 모든 수를 나눠볼 필요가 없다.

 

[그래서 최종 작성한 코드]

 

 

def solution(n):
#     1 5 25 
# ex 26
    ans=0
    for x in range(2,n+1):
        cnt=0
        for i in range(2,int(x**(1/2))+1):
    #         소수가 아닐때
            if x%i==0:
                cnt+=1
                break
        if cnt==0:
            ans+=1
    return ans

- for x in range에서 어차피 1은 의미가 없으므로 2부터 range 설정해주기

- 소수 판별하기 위해 나눠줄 때 x의 제곱근 만큼만 for문 돌려주기 !! 

- (중요) if x%i==0이 성립하면 소수가 아니므로 바로 break 해주기 

 

그 결과

 

 

 

 

통과완료 ㅎㅎ