[Python/프로그래머스] 12921_소수 찾기 ★★★

 

 

[문제]

문제 설명

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

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

제한 조건

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

입출력 예

n	result
10	4
5	3

 

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

 

[1차 풀이]

- 뭘 해도 효율성에서 실패한다.

def solution(n):
    li = []
    for i in range(2,n+1):
        incontinue = True
        for x in li:
            if i%x == 0:
                incontinue = False
                break
        if incontinue:
            li.append(i)
    return len(li)

 

 

[2차 풀이]

- 에라토스테너스의 체를 이용하여 풀면 된다고 한다.

- 에라토스테너스의 체 : n의 제곱근까지 소수를 구한 후, 그 소수의 배수들을 제외한 나머지 수는 모두 소수가 된다고 한다.

- 코드가 복잡하여 다른 코드를 참조해 풀어보도록 하자.

- 1) 내부 while 코드 부분을 수정해보자.

  2) 초반에 n개 수만큼 값이 1인 list를 만들어 index로 찾아내 0값으로 세팅해줬는데, 모두 1값이 아닌 2~n값으로 한번 풀어봐야겠다.

 

def solution(n):
    li = [1 for i in range(1,n+1) ]
    li[0] = 0 
    idx = 2
    limit = n**(1/2)+1
    while idx < limit:
        for i in range(2, idx+1):
            if li[idx-1] != 0 and idx % i == 0:
                temp = idx
                x = 2
                while True:
                    temp = idx * x
                    if temp > n:
                        break
                    li[temp-1] = 0
                    x = x+1
        idx = idx+1
    print(li)
    return sum(li)

 

[3차 풀이]

- list - list 를 이용하기 위해 set으로 만들어 사용했다.

def solution(n):
    li = set([i for i in range(2,n+1)])
    idx = 2
    # n제곱근 개수 만큼.
    limit = n**(1/2)+1
    while idx < limit:
        for i in range(2, idx+1):
            if idx % i == 0 :
                # 나누어 떨어 지는 것이 있으면 그 idx의 배수 지우기
                li = li - set(range(idx*2, n+1, idx))
        idx = idx+1
    return len(li)

 

 

[4차 풀이]

- ★★★★ 2부터 n까지 for문을 수행하며 배수만 지워주면, 소수가 구해지는 간단한 방식이 있었다.

def solution(n):
    li = set(range(2,n))
    for i in range(2, n+1):
        if i in li:
         #idx의 배수 지우기
            li -= set(range(i*2, n+1, i))
    return len(li)

 

 

[링크]

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

프로그래머스