[파이썬] 소수 구하기

programmers.co.kr/learn/courses/30/lessons/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를 반환

 

✨ 나의 풀이

 

# 몇 개가 시간 초과
def solution(n):
    answer = 0
    def check(i):       # 소수인지 판별하는 함수
        for j in range(2, i//2+1):
            if i%j == 0:
                return False
        return True
    for i in range(2, n+1):
        if check(i):
            answer+=1
    return answer

 

연산과정 땜에 오래걸리는 듯... 

check함수에서 i//2+1까지 반복한 이유는 아래를 참고했다.

 

ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

def solution(n):
    a = [False, False] + [True]*(n-1)		# False는 0과 1, True는 초기값
    primes=[]

    for i in range(2, n+1):
        if a[i]:					# 인덱스 번호에 맞춰서 True/False
            primes.append(i)
        for j in range(2*i, n+1, i):
            a[j] = False
    return len(primes)

 

https://wikidocs.net/21638

위키독스

 

여기에 나온 에라토스테네스를 이용한 소스 코드를 썼더니 통과했다.

2부터 시작한 이유는 1은 소수가 아니니까 볼 필요가 없어서. 

range(2*i, n+1, i)가 이해가 안 갈수도 있다. 

 

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

1. 1은 제거 -> 첫번째 반복문에서 2부터 시작함.

2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다. -> 2*i에서 시작, i만큼 증가하는 것은 = 배수찾기

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

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

5. (반복)

 

2*i보다 i*2로 보는 것이 더 이해하기 편할 것 같다. 

 

 

🎀 다른사람 풀이

 

def solution(n):
    num=set(range(2, n+1))		# 2에서 n까지 set으로 저장

    for i in range(2, n+1):
        if i in num:			# if조건 생략가능
            num-=set(range(2*i, n+1, i))
    return len(num)

 

2에서 n까지 set인 num에 저장. if조건을 왜 넣은건지 이해가 안된다(없어도 됨).

차집합을 이용해서 i의 배수들을 없앤다.

 

# 실패(시간초과)
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

 

나랑 같은 알고리즘을 씀. 문제가 변경된 이후라 이 코드는 시간 초과 뜬다. 

결론 : 이 문제는 에라토스테네스의 체를 이용해서 풀자!!