[프로그래머스 Level 1] 소수 찾기 - 파이썬(Python)

문제 설명

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를 반환

 

나의 풀이

 

def solution(n):
    n = n + 1
    answer= [True] * n
    for i in range(2,int(n**0.5)+1):
        if answer[i] == True:
            for j in range(i+i,n,i):
                answer[j]=False
    a=[i for i in range(2,n) if answer[i]== True]

    return len(a)

1. 리스트 answer을 모두 소수라고 생각해 True로 값을 설정합니다.
2. 2부터 int(n**0.5)까지 소수인지 확인합니다.
   int(n**0.5)인 이유는 n의 최대 약수가 int(n**0.5)이하이기 때문입니다.
3. 2번에서 소수인 숫자의 배수들은 소수가 아니기 때문에 다음 for문에서 소수가 아니라고 False로 설정해줍니다.
4. 2번과 3번의 과정을 반복합니다.
5. 리스트 answer의 값이 True인(소수인 것) 값들의 개수를 리턴합니다.

다른 사람의 풀이

 

def solution(n):
    num=set(range(2,n+1))
    print('num',num)

    for i in range(2,n+1):
        if i in num:
            num-=set(range(2*i,n+1,i))
    return len(num)

2부터 n까지 중복제거한 리스트를 생성합니다.
2부터 n까지 소수인지 확인하는 과정에서 소수인 숫자의 배수들은 set을 통해 제거하여 num을 설정해줍니다.
이 과정을 반복하고 num의 길이를 리턴합니다.

---

프로그래머스 '소수 찾기' : https://programmers.co.kr/learn/courses/30/lessons/12921

코딩테스트 연습 - 소수 찾기