프로그래머스 소수 찾기 시간초과, 효율성 테스트

프로그래머스 Lv1 소수 찾기 문제를 푸는 도중 답은 나오는데 시간 초과로 넘어가질 않아서 정리해본다. 

def prime(x):
    cnt = 0
    if x == 1: return False
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            cnt +=1
    return True if cnt==0 else False
 
 
def solution(n):
    return sum([int(prime(i)) for i in range(1, n+1)])

소수 구하는 prime 함수를 만들어서 n까지 숫자를 넣어 실행 시켰더니 정답은 나오는데 

시간 초과로 넘어가질 않네;; 

에라토스테네스의 체도 사용했는데 왜 안넘어 가는것이냐

제한 조건으로 이게 있구나...

n은 2이상 1000000이하의 자연수입니다.

 

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

def solution(n):
    return sum([int(prime(i)) for i in range(2, n+1)])

x라는 숫자가 소수인지 판별하기 위해서 2부터 x까지 수(1은 소수가 아니니까)를 넣어서 나누어 떨어지는지 확인해야하는데

첫번째 코드에선 나누어 떨어지면 cnt+=1을 해서 1개라도 있다면 소수가 아니니까 False를 cnt==0 이면 True를 뱉도록했는데 

이게 안넘어 가니까!!!!!!!!!!!!!

 

2부터 나누는데 나누어 떨어지는게 있으면 소수가 아니니까 바로 False로 리턴하도록 

그리고 떨어지는게 없으면 True로 리턴하도록 바꾸니까 통과됐다.

 

아마도 cnt에 더하면 아무리 x의 제곱근까지만 간다고해도 O(N)의 시간 복잡도가 걸리기 때문에 실패한거 같다.

하지만 나누어 떨어질때 바로 return 해버리면 for문을 다 안도니까 통과한거 같은데 맞나??