(Python) *소수 찾기 (프로그래머스 Lv.1)

(Python) 소수 찾기 (프로그래머스 Lv.1)

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

프로그래머스

 

처음 내 코드

def solution(n):
    answer = 0
    if n>= 2:
        answer += 1
        
    for i in range(3,n+1):
        for j in range(3,i):
            if (i % j) == 0:
                break
            elif j == (i-1): 
                answer+=1
    return answer

처음 이것을 제출했으나 테스트 10,11,12와 효율성 테스트에서 시간 초과를 하였다.

n이 최대 100만개이기 때문이다.

찾아보다가 

특정한 숫자의 제곱근까지만 약수의 여부를 검증하면 된다

라는 힌트를 얻게되어 다시 코드를 짜보았다. 

한 함수안에서 짜려다보니 순서에 애를 먹었는데 하도 안풀려서 다른 분이 하싱걸로 보니 다른 함수를 또 만들어서 하는 걸보고 아차 싶었다 코드는 아래와 같다.

def isPrime(n):
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

def solution(n):
    answer = 0
    for i in range(2, n+1):
        if isPrime(i) == True:
            answer += 1
    return answer