[Python]프로그래머스 LEVEL1> 소수 찾기

안녕하세용! 오늘은 프로그래머스,, 소수찾기 부분을 가져왔습니당

이번 문제는 에라토스테네스의 체만 알고있었다면 금방 풀 수 있었을 문제였다 ㅎㅎㅎ

 

문제 설명

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

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

제한 조건

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

입출력 예

nresult

10	4
5	3

입출력 예 설명

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

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

 

풀이과정

소수를 찾는 과정을 저는 에라토스테네스의 체를 이용해 풀었다.

 

여기서 에라토스테네스의 체에 대한 이야기는 따로 ,, 포스팅 할것이지만..

간단하게 말하자면.. 2부터 시작해 가장 작은 수를 소수로 두고 다음으로 2의 배수들을 지우고 지워지지 않은 숫자중 가장 작은수를 소수로 두고 또 3의 배수들을 다 지운다 이런식으로 반복해 소수를 찾는건데.. 소수찾기에 가장 정확한 방법이라고 하니 정말 좋은 기능인것 같다.

 

내 풀이과정을 적어보자면

처음 주어진 숫자(n)만큼의 T/F을 리스트로 두고 (0,1은 소수가 아니기 때문에 False로 두었다)

if문을 두어 만일 가장 작은수가 True라면 그 작은수에 대한 배수들을 모두 False로 바꾸고 t의 리스트에 가장 작은수(즉 소수)를 넣어 주어진 값(n)안의 소수개수를 찾을 수 있었다.

나는 소수의 개수만 return값으로 내면 되기에 T/F로 코딩했지만 range를 써 숫자로 두고 에라토스테네스를 써도 될것같다. ㅎㅎ

 

 

 

def solution(n):
    t=[]
    P=[False,False]+[True]*(n-1)
    for i in range(2,n+1):
        if P[i]==True:
            for z in range(i,n+1,i):
                P[z]=False
            t.append(i)
        
            
    return len(t)