2020. 5. 6. 21:13

[python](프로그래머스)소수 찾기

문제 설명


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

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

 

제한 조건


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

 

문제 풀이


def numberOfPrime(n):
    sum = 0
    s = 0
    for i in range(2,n+1):
        for j in range(2,i):
            if i % j == 0:
                s += 1
        if s == 0:
            sum += 1
        s = 0
    return sum

일반적인 코드로 짠다고하면 이중 포문으로 2부터 끝까지 해당하는 숫자까지를 다 나눠서 0으로 딱떨어지면 소수이므로 count를 하는 변수를 넣거나 배열에 넣어두었다가 lenth를 세게 만든다.

하지만 이중포문은 숫자가 늘어날 수록 시간복잡도가 제곱배로 늘어나게 되므로 다소 무식한 방법일 수가 있다. 이럴 때 사용하는 방법이 에라토스테네스의 체이다.

에라토스테네스의 체란 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법이다.

  1. 1은 제거
  2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.
  3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.
  4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.
  5. 반복

이 에라토스테네스의 체를 응용해서 문제를 풀어보면 다음과 같은 코드가 나온다.

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

 

다른 풀이


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

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

역시나 에라토스테네스의 체를 이용한 방법, 미리 set으로 해당하는 n까지의 범위를 정해놓고 그 범위에서 소수가 아닌 것을 제외한다.