[level 1] 소수 찾기(에라토스테네스의 체 다시)

문제

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

 

 

문제 풀이 접근법1

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

제일 간단한 방법으로 해보았다..

테스트 케이스 10, 11, 12에서 실패하고 효율성 테스트 1, 2, 3, 4 당연히 실패했다 ^~^

 

 

문제 풀이 접근법2

약수를 판별할 때 √n 만큼 확인하면 된다는 점을 이용해서 풀어보았다.

import math
def solution(n):
    answer = 0
    
    for i in range(2, n+1):
        count = 0
        for j in range(2, int(math.sqrt(i)+1)):
            if i % j == 0:
                count +=1
        if count < 1:
            answer +=1
        
           
    return answer

테스트 케이스 11, 효율성 테스트에서 실패했다. 

 

문제 풀이 접근법3

에라토스테네스의 체...알고리즘을 사용해서 풀어보았다. 에라토스테네스의 체는 범위에 대한 소수 판별에 유리하다고 한다. 

1) 2부터 N까지의 모든 자연수를 나열한다.

2) 남은 수 중에 아직 처리하지 않은 가장 작은 수(이자 소수인)  i를 찾는다.

3) 남은 수 중에서 i의 배수 제거한다.(i는 제거하지 않는다.)

4) 2, 3의 과정을 계속 반복한다.

출처: https://velog.io/@koyo/python-is-prime-number

[내가 보려고 적는 파이썬] 소수 판별(에라토스테네스의 체)

def solution(n):
    answer= []
    numbers = []

    for i in range(n+1):
        numbers.append(True)

    nums = int(n**0.5)

    for i in range(2, nums+1):
        if numbers[i] == True:
            j = 2
            while i*j <= n:
                numbers[i*j] = False
                j+=1


    answer = [i for i in range(2, n+1) if numbers[i]]
    
    return len(answer)

하 문제 풀다가 성격 버릴 뻔

사실...에라토어쩌구...잘 모르겠다.

이건 좀 다시 해봐야겠음

 

---

다른 분들 풀이

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)

와 똑똑하다...

나도 내일(=0810) 에라토스테네스의 체 다시 구현해봐야겠다...!!