★[Programmers/Level 1]소수 찾기

 

퓨ㅠ 시간초과

import math
def solution(n):
    arr = [1] * (n+1)
    print(int(math.sqrt(n))+1)

    for i in range(2,int(math.sqrt(n))+1):        
        if(arr[i] == 1):
            for j in range(i*i, n+1):          
                if(j%i == 0): arr[j] = 0
                    
    return arr.count(1) - 2 #0과 1 제외

정확성 테스트

테스트 1 〉	통과 (0.04ms, 10.7MB)
테스트 2 〉	통과 (0.10ms, 10.8MB)
테스트 3 〉	통과 (0.18ms, 10.7MB)
테스트 4 〉	통과 (0.42ms, 10.7MB)
테스트 5 〉	통과 (0.25ms, 10.7MB)
테스트 6 〉	통과 (7.15ms, 10.8MB)
테스트 7 〉	통과 (1.35ms, 10.8MB)
테스트 8 〉	통과 (4.58ms, 10.7MB)
테스트 9 〉	통과 (8.88ms, 10.8MB)
테스트 10 〉	통과 (939.59ms, 12.5MB)
테스트 11 〉	통과 (4774.87ms, 17.3MB)
테스트 12 〉	통과 (1031.34ms, 12.7MB)

효율성 테스트

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

채점 결과

정확성: 75.0

효율성: 0.0

합계: 75.0 / 100.0

통과한건

import math
def solution(n):
    arr = [1] * (n+1)
    print(int(math.sqrt(n))+1)

    for i in range(2,int(n ** 0.5)+1):        
        if(arr[i] == 1):
            for j in range(i*i, n+1, i):          
                arr[j] = 0
                    
    return arr.count(1) - 2 #0과 1 제외

채점을 시작합니다.

정확성 테스트

테스트 1 〉	통과 (0.06ms, 10.8MB)
테스트 2 〉	통과 (0.07ms, 10.8MB)
테스트 3 〉	통과 (0.09ms, 10.8MB)
테스트 4 〉	통과 (0.11ms, 10.7MB)
테스트 5 〉	통과 (0.12ms, 10.8MB)
테스트 6 〉	통과 (0.66ms, 10.8MB)
테스트 7 〉	통과 (0.21ms, 10.7MB)
테스트 8 〉	통과 (0.49ms, 10.8MB)
테스트 9 〉	통과 (0.79ms, 10.8MB)
테스트 10 〉	통과 (23.12ms, 12.6MB)
테스트 11 〉	통과 (82.38ms, 17MB)
테스트 12 〉	통과 (26.19ms, 12.8MB)

효율성 테스트

테스트 1 〉	통과 (86.78ms, 17.8MB)
테스트 2 〉	통과 (84.41ms, 17.5MB)
테스트 3 〉	통과 (86.79ms, 17.6MB)
테스트 4 〉	통과 (98.56ms, 17.6MB)

채점 결과

정확성: 75.0

효율성: 25.0

합계: 100.0 / 100.0

if문 하나 줄었더니 통과...

if문 허투루 쓰지 않도록 습관들여야겠다

 

---

다른 분 코드

def solution(n):
    num=set(range(2,n+1))

    for i in range(2,n+1):
        if i in num:
            num-=set(range(2*i,n+1,i))
    return len(num)

미침..어떻게 이런 생각하지

이렇게 푸는거 아예 외워야겠다 담에 이거 또풀어봐야징