프로그래머스 Lv1. 소수찾기 문제링크

오답코드

import math

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

def primenumber(x):
    for i in range(2,x):	
    	if x % i == 0:	
        	return False
    return True	

이렇게 써서 제출했는데 시간초과가 났다.

정답코드

import math

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

def primenumber(x):
    # 특정한 숫자의 제곱근까지만 약수의 여부를 검증하면 된다
    for i in range(2, int(math.sqrt(x))+1):	
    	if x % i == 0:	
        	return False
    return True	

반복문의 범위 설정 시에 입력받은 숫자까지 약수의 여부를 검증할 필요가 없다. 입력받은 숫자의 제곱근까지만 약수의 여부를 검증하면 시간초과를 막을 수 있다.