211230_Code in the morning(소수찾기, 에라토스테네스의 체)

Code in the morning, 매일 아침 알고리즘 문제를 풉니다. 

💬 문제 설명: 소수 찾기

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

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

 

 

📍 제한 사항

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

 

 

💡 나의 풀이 

from collections import Counter 

def solution(n):
    num = []
    # 소수를 찾는 식 
    for i in range (1,n+1):
        for j in range (1, n+1):
            if i % j == 0:
                num.append(i)
    
    cnt = Counter(num)
    a = []
    for i in range (1, n+1):
        if (cnt[i] == 2):
            a.append(i)
    return(len(a))

나의 풀이는:

1. n까지의 소수를 리스트로 받아오고, 

2. 소수를 골라내서 

3. 갯수를 세기 였는데, 

위의 방법으로 하니 시간 초과로 실패하게 되었다. ㅠㅠ

 

* Counter 함수: 

Counter의 함수는 컨테이너등에 동일한 자료가 몇 개인지 확인하는 데 사용하는 객체이다. 

from collections import Counter
 
list = ['Hello', 'HI', 'How', 'When', 'Where', 'Hello']
print(Counter(list))




#결과물 
>>>Counter({'Hello': 2, 'HI': 1, 'How': 1, 'When': 1, 'Where': 1})

💡 다른 해설

* 에라토스테네스의 체

에라토스테네스가 고안한 소수를 찾는 방법으로, 이 방법으로 소수를 찾으려면 2부터 시작해 자연수를 차례로 쓴 다음, 2 이외의 2의 배수, 3 이외의 3의 배수, 5 이외의 5의 배수의 순서로 수를 지워나가 끝에 남는 수가 소수이다.

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)

 

* set 집합에서 원소를 -로 바로 뺄 수 있나보다. 

 

 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

👉🏻 문제 바로가기