[프로그래머스]소수찾기_효율성 테스트 통과하기

프로그래머스

내가 짠 코드 - 효율성 테스트 통과 실패

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

    return answer

해결 방향
1. n^2되는 문제 해결하기
2. 수의 특징을 활용하여 소수 판별 함수에서 for문의 반복 횟수 줄이기
3. 에라스토테네스의 체 사용해서 소수가 될 수 없는 수 미리 계산하여 반복문 횟수 줄이기

리더가 다시 짜 준 코드 

# math.sqrt위한 import
# sqrt는 제곱근, 루트
import math

# 프라임 판별 함수
def isprime(a) :
		# 2부터 루트a까지 for문 돌면서 나눠지는지 확인
    for i in range(2,int(math.sqrt(a))+1) :
        if a%i == 0:
            return False
    return True

def solution(n):
    answer = 0
		# index를 prime판별할 수라고 생각하시면 됩니다
		# prim[i] = 0 이면 소수임 ( 0과 1 제외 )
    prime = list(0 for _ in range(n+1))
    for i in range(2,n+1) :
				# 소수가 가능한 숫자이면
        if prime[i] == 0 :
						# 소수인지 판별
            if isprime(i) :
                answer += 1
						# 해당 수의 배수는 모두 소수가 아니므로 1로 초기화
            j = 0
            while i*j<=n :
                prime[i*j] = 1
                j += 1
        else :
            pass
    return answer

에라스토테네스 체 없이 풀기 

import math
def solution(n):
    answer = 0
    for x in range(2, n+1) :
        for y in range(2,int(math.sqrt(x))+1) :
            if x%y == 0 :
                answer += 1
                break
    return n-(answer+1)
# 제곱근까지 for문 돌고 나눠지는 순간(소수아님)
# break으로 for문 빠져나오기
# 이후 전체 경우의 수에서 소수 아닌 것들 빼줬습니다

우리 러닝 메이트 리더 대단한 사람이다....