[프로그래머스] 소수 찾기

📖 문제

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

💻 내 코드

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)

💡 풀이

• 에라토스테네스의 체 사용

에라토스테네스의 체

• 소수를 판별하는 알고리즘
• 2의 배수, 3의 배수, 5의 배수, 7의 배수...를 제거하면 소수만 남음

다른 방법으로 에라토스테네스의 체 사용

def prime_list(n):
    sieve = [True] * n
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:         
            for j in range(2*i, n, i):
                sieve[j] = False

    return [i for i in range(2, n) if sieve[i] == True]

• 어떤 자연수 n이 있을 때, √n 보다 작은 모든 소수들로 나누어 떨어지지 않으면 n은 소수
  
  
  
• 처음 제출했던 코드들은 시간 초과가 되고 효율성 테스트를 통과하지 못함

원래 제출했던 코드들

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

def solution(n):
    answer = 1
    
    for i in range(3,n+1):
        s=0
        if i%2==0:
            continue
        for j in range(1, n+1):
            if i%j==0:
                s+=1
                if s>2:
                    continue
        if s==2:
            answer+=1
    
    return answer

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

• 2부터 자기자신-1 까지 for문을 돌려 나누어 떨어지는 수가 있다면 break
• 만약 break가 되지 않았다면 answer+1

for-else 문: for 문이 중간에 break 등으로 빠져나오지 않고 끝까지 실행됐을 경우 else문을 실행한다