[프로그래머스] 12921번 : Lv1 소수 찾기 | 에라토스테네스의 체

[프로그래머스] 12921번 : Lv1 소수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

---

 

[python] 문제 풀이

1. 1부터 n까지의 숫자를 a로 불러오기

2. a를 2~(a-1)까지 나누기 

3. 나머지 값이 0이면 소수가 아님 ->종료

def solution(n):
    prime = []  # 소수를 저장할 리스트

    # 2부터 n-1까지의 숫자(a)에 대해 반복
    for a in range(2, n+1):
        # number가 소수인지 확인
        for i in range(2, a):
            if a % i == 0:  # 나머지 값이 0이면 소수가 아님
                break  # 소수가 아님, 루프 중단
        else:
            # for 루프가 break 없이 끝나면 소수
            prime.append(a)
    
    answer = len(prime)  # 소수의 개수 반환
    return answer

다음과 같이 코드를 작성했다.

 

그런데 테스트 케이스 오류 발생했다.

 

 

지피티한테 물어보니 소수를 찾는 방식이 비효율적이고 모든 숫자를 다 나누어 보는 방식은 숫자가 커질수록

연산이 매우 느려져서 그렇다고 한다. 

 

효율성을 개선하기 위해 다음과 같은 해결책을 제시했다.

 

제곱근까지만 나누기 : a의 제곱근까지만 확인하면 된다. 어떤 수가 소수가 아니라면, 그 수는 반드시 두 수의 곱으로 표현 된다. 그 중 하나의 수는 반드시 제곱근 이하이므로 제곱근까지만 확인하면 된다.

 

def solution(n):
    prime = []  # 소수를 저장할 리스트

    # 2부터 n-1까지의 숫자(a)에 대해 반복
    for a in range(2, n+1):
        # number가 소수인지 확인
        for i in range(2, int(a**0.5) + 1):
            if a % i == 0:  # 나머지 값이 0이면 소수가 아님
                break  # 소수가 아님, 루프 중단
        else:
            # for 루프가 break 없이 끝나면 소수
            prime.append(a)
    
    answer = len(prime)  # 소수의 개수 반환
    return answer

이렇게 수정하니 테스트 케이스를 통과하고 채점이 완료되었다.

 

많이 좋아지긴 했지만 여전히 너무 느리다.

 

---

[추가] 에라토스테네스 체

---

 

1. 초기화: 모든 숫자를 소수로 가정한 리스트를 생성

2. 소수 판별 및 배수 제거:

•  현재 숫자가 소수라면, 그 숫자의 배수들을 비소수로 표시
•  이 과정을 sqrt{n}까지 반복

3. 소수 개수 계산: 리스트에서 True 값을 세어 소수의 개수를 반환

 

---

 

def solution(n):
    # n+1 길이의 True 리스트 생성 (소수 여부를 표시)
    sieve = [True] * (n + 1)
    
    # 0과 1은 소수가 아니므로 False로 설정
    sieve[0] = sieve[1] = False

    # 2부터 sqrt(n)까지 반복하면서 배수들을 False로 표시
    for i in range(2, int(n**0.5) + 1):
        if sieve[i]:  # i가 소수일 경우 (True 인 경우)
            for j in range(i*i, n + 1, i):  # i의 배수들을 False로 설정
                sieve[j] = False

    # sieve에서 True인 인덱스가 소수이므로 개수 세기
    prime = [i for i in range(2, n + 1) if sieve[i]]
    
    answer = len(prime)
    return answer

 

            for j in range(i*i, n + 1, i):  # i의 배수들을 False로 설정
                sieve[j] = False

i*i보다 작은 배수들은 이미 더 작은 소수의 배수로 처리됨. 

i*i 부터 n 까지의 i 만큼의 간격으로 j 값을 증가시키면서 반복.

즉, i*i , i*(i+1), i*(i+2), ... 등 i의 배수들이 모두 포함.

 

    # sieve에서 True인 인덱스가 소수이므로 개수 세기
    prime = [i for i in range(2, n + 1) if sieve[i]]

 

sieve 값이 true 일 때 (소수 일때) 2부터 n까지의 인덱스 i 값을 prime 리스트에 저장.

 

 

 

예시) n= 10 일때,
sieve=[False, False, True, True, False, True, False, True, False, False, False]
sieve[2] = True, sieve[3] = True, sieve[5] = True, sieve[7] = True
따라서, prime = [2,3,5,7]

 

 

 

prime 리스트 없이 sieve 배열에서 true 값의 갯수만 셀 수도 있다.

def solution(n):
    # n+1 길이의 True 리스트 생성 (소수 여부를 표시)
    sieve = [True] * (n + 1)
    
    # 0과 1은 소수가 아니므로 False로 설정
    sieve[0] = sieve[1] = False

    # 2부터 sqrt(n)까지 반복하면서 배수들을 False로 표시
    for i in range(2, int(n**0.5) + 1):
        if sieve[i]:  # i가 소수일 경우
            for j in range(i*i, n + 1, i):  # i의 배수들을 False로 설정
                sieve[j] = False

    # True인 값의 개수를 세서 반환 (소수의 개수)
    return sum(sieve)

 

 

 

 

 

 

 

 

 

---

 

1부터 100까지 숫자 나열

소수도 합성수도 아닌 유일한 자연수 1 제거 

 

 

2를 제외한 2의 배수 제거

3을 제외한 3의 배수 제거

 

 

4의 배수는 지울 필요 없음. 5의 배수 제거.

마지막, 7의 배수 제거

8,9,10의 배수는 이미 지워졌음. 11이상의 소수는 √100보다 크기 때문에 지울 필요 없음.