알고리즘_코딩도장_소수의 개수 구해보기

### 소수란?
- 1과 자기 자신으로밖에 나누어떨어지지 않는 1 이외의 정수. 소수의 정의는 '1과 자기 자신으로밖에 나누어 떨어지지 않고 자기 자신의 곱셈의 역수가 없는 수'이다.
- 뭐 간단히 얘기하면 홀수에서만 소수를 찾을 수 있다는 뭐 심플한 말이다. 뭐이리 어렵게 설명해놓는지...

- 2는 유일한 짝수 중에서 소수다. 외롭다

 

### 문제와 참고 사이트 링크

문제: codingdojang.com/scode/503?answer_mode=hide

코딩도장

에라토스테네스의 체

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

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

첫번째 답(위키 참고)

# wiki 정석?
# 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
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(i+i, n, i):
                sieve[j] = False
    return [i for i in range(2, n) if sieve[i] == True]

 

두번째 답(제가 풀은 방법)

def answer(x):
    num_list = [i for i in range(2, x+1)]
    prime_list = [2] # 2는 미리 세팅
    for i in num_list:
        for j in range(2,i):
            if (i%j) == 0:
                break
            else:
                prime_list.append(i)
    return prime_list
    
 
 list(set(answer(1000)))

1. set을 이용해서 중복 제거하기

집합 자료형은 다음과 같은 특징이 있습니다.

1) 중복을 허용하지 않는다.

2) 순서가 없다.

이 두 가지 특징 중 첫 번째 특징을 이용하면 손쉽게 리스트 요소의 중복을 제거할 수 있습니다.

 

그리고 list로 만들어 주면
짜라잔~ 중복된 숫자를 사라지고, 소수들만 남는 리스트 값을 뽑아낼 수 있습니다.