[프로그래머스] <소수 찾기> 파이썬

programmers.co.kr/learn/courses/30/lessons/12921

코딩테스트 연습 - 소수 찾기

 

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

정확성 테스트

테스트 1 〉	통과 (0.00ms, 10.1MB)
테스트 2 〉	통과 (0.25ms, 10.3MB)
테스트 3 〉	통과 (1.37ms, 10.2MB)
테스트 4 〉	통과 (3.82ms, 10.1MB)
테스트 5 〉	통과 (1.95ms, 10.2MB)
테스트 6 〉	통과 (207.65ms, 10.1MB)
테스트 7 〉	통과 (20.24ms, 10.2MB)
테스트 8 〉	통과 (112.08ms, 10.2MB)
테스트 9 〉	통과 (282.97ms, 10.1MB)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	실패 (시간 초과)
테스트 12 〉	실패 (시간 초과)

효율성 테스트

테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)

채점 결과

정확성: 56.3

효율성: 0.0

합계: 56.3 / 100.0

 

에라토스테네스의 체...

import math
def solution(n):
    answer = [1]*(n+1)
    answer[0], answer[1] = 0, 0
    for i in range(2,int(math.sqrt(n))+1):
        if answer[i] == 0 : continue
        j = i
        while True :
            j += i
            if j > n : break
            answer[j] = 0

    return answer.count(1)

정확성 테스트

테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.03ms, 10.2MB)
테스트 3 〉	통과 (0.07ms, 10.2MB)
테스트 4 〉	통과 (0.16ms, 10.2MB)
테스트 5 〉	통과 (0.53ms, 10.3MB)
테스트 6 〉	통과 (1.56ms, 10.2MB)
테스트 7 〉	통과 (0.44ms, 10.2MB)
테스트 8 〉	통과 (1.17ms, 10.1MB)
테스트 9 〉	통과 (1.77ms, 10.2MB)
테스트 10 〉	통과 (42.41ms, 12.1MB)
테스트 11 〉	통과 (137.67ms, 16.7MB)
테스트 12 〉	통과 (46.75ms, 12.5MB)

효율성 테스트

테스트 1 〉	통과 (154.47ms, 17MB)
테스트 2 〉	통과 (148.79ms, 16.7MB)
테스트 3 〉	통과 (147.78ms, 17.1MB)
테스트 4 〉	통과 (145.35ms, 17.1MB)

채점 결과

정확성: 75.0

효율성: 25.0

합계: 100.0 / 100.0