[수학] [BJ1929] 소수 구하기

코드 플러스

🚩 문제 설명

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

⏱️ 시간 복잡도
▪ 총 N개의 수가 있다.
▪ 해당 수열에서 어떤 수가 소수인지 알아내는 데에는 O(abs(N)) 이 걸린다.
▪ N개의 수열 중에서 모든 소수를 찾는 데에는 O(N x abs(N)) 이 걸린다.
▪ 해당 문제에서 N의 최대 범위가 100만 이므로 총 시간복잡도는 10^9가 되고 이는 시간초과를 일으킨다.
▪ 따라서 에라토스테네스의 체 라는 방식으로 소수를 구하면 O(NlogN)으로 좀 더 빠르게 풀 수 있다.

◾ 특정 범위 안의 소수를 찾아 출력하는 문제

◾ 에라토스테네스의 체

1. 2부터 N까지 모든 수를 써놓는다.
2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.
3. 그 수는 소수이다.
4. 그 수의 배수를 모두 지운다.

prime = [0] * N  # 소수 저장
memo = [0] * (N + 1)  # 소수 메모이제이션
pCnt = 0  # 소수의 개수

for i in range(2, N + 1):

    # 만약 지워지지 않았다면
    if memo[i] == 0:
        pCnt += 1
        prime[pCnt] = i

        # 배수를 지우는 과정
        for j in range(i * i, N + 1, i):
            memo[j] = 1

print(prime)
print(pCnt)

 

 

 

---

 

 

 

✅ 입출력

1) 범위를 나타내는 M과 N이 주어진다.
return ➡️ M과 N 사이의 소수를 모두 출력한다.

✔️ 예제 1

3 16

3
5
7
11
13

 

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

import sys

M, N = map(int, sys.stdin.readline().split())

prime = [0] * N  # 소수 저장
memo = [0] * (N + 1)  # 소수 메모이제이션
pCnt = 0  # 소수의 개수

for i in range(2, N + 1):

    # 만약 지워지지 않았다면
    if memo[i] == 0:
        pCnt += 1
        prime[pCnt] = i

        # 배수를 지우는 과정
        for j in range(i * i, N + 1, i):
            memo[j] = 1

for i in prime:
    if i >= M:
        print(i)

 

 

💬 Point

➡️  에라토스테네스의 체 사용
➡️  memo 라는 배열을 통해 memoization 사용

◾ 우선 범위에 해당하는 M과 N을 입력받는다.

◾ 그런 다음 에라토스테네스의 체를 사용하여 만약 memo에 체크되지 않았다면

◾ 카운트를 하고 그 해당 카운트 인덱스에 값을 넣어준다.

◾ 그리고 해당 값의 배수를 지워준다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

# 코드 플러스 소수 구하기 파이썬 python

# 백준 1929 소수구하기 파이썬 python

---