[ 파이썬(python) ] 프로그래머스 level1 - 소수판별

📌 소수 판별

기존에 나동빈 - 이코테 책에서 봤던 유형이었는데, 소수문제에는 2가지 유형이 있다.

1. 입력값이 단순히 소수인지 판별할 때
2. 입력 구간에서 소수값 출력

 

이 문제는 2번 유형에 가까운 문제였다. 1부터 n까지의 소수의 개수를 구하는 문제기 때문이다. 정답을 제출하고 다른사람의 코드를 보는데 신기한 코드가 있었다. set을 활용해서 반복문을 돌때마다 i의 배수만큼 빼주는 코드가 있었다. 코드도 파이써닉했는데, 한눈에 이해가 되고 깔끔했다. 앞으로 이렇게 코드를 작성하도록 노력해야겠다.

---

💡 나의 풀이

에라토스테네스의 체를 이용해 풀었다. 여기서 반복문의 범위를 2부터 제곱근까지 선언한 이유는 약수의 특징을 이용했는데, 예를 들어 10은 가운데 약수를 기준으로 대칭적으로 2개씩 앞뒤로 묶어서 곱하면 10이 된다. (1*10, 2*5, 5*2, 10*1)

제곱근까지만 계산을 해주면 제곱근 뒤는 이미 앞에서 계산했기 때문에 False로 바뀐다. 시간복잡도면에서 효율적인 계산이다. 잠깐 팁을 알아보자면, 제곱근은 다음처럼 선언할 수 있다.

1. range(2, int(n**0.5) +1)
2. range(2, round(n**0.5) +1)
3. range(2, int(math.sqrt(n))+1)

728x90

풀이방법은 다음과 같다.

1. n+1만큼 True 선언
2. 2부터 제곱근까지 array[i] == True면, i의 배수만큼 array[i]를 False로 바꿔준다.
3. 반복문을 통해 False로 바뀐 index를 출력하면 된다.
   
   

# 나의 풀이 
def solution(n):     
  array = [True for i in range(n+1)]      
  for i in range(2, int(math.sqrt(n))+1):         
    if array[i]:             
      j = 2             
      while i * j <= n:                 
        array[i*j] = False                 
        j+=1      
        result = [i for i in range(2, n+1) if array[i]]     
        return len(result)      
        
# 방법 1 
def solution(n):     
  numbers = set(range(2, n+1))      
  for i in range(2, int(n**0.5)+1):         
    numbers -= set(range(2 * i, n + 1, i))      
    return len(numbers)  
    
# 방법 2 
def solution(n):     
  numbers = set(range(2, n+1))      
  for i in range(3, int(n**0.5)+1):         
    numbers -= set(range(i * i, n + 1, i))      
    return len(numbers)