정수론
07-1 소수 구하기
- 소수 prime number는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말한다.
- 즉, 1과 자기 자신 외에 약수가 존재하지 않는 수이다.
- 코딩 테스트에 소수를 판별하는 방식을 묻는 소수 구하기 문제가 종종 출제된다.
[소수 구하기의 핵심 이론 - 에라토스테네스의 체]
1. 구하고자 하는 소수의 범위만큼 1차원 리스트를 생성한다.
2. 2부터 시작하고 현재 숫자가 지워진 상태가 아닌 경우, 현재 선택된 숫자의 배수에 해당하는 수를 리스트에서 끝까지 탐색하면서 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다.
3. 리스트의 끝까지 2번 과정을 반복한 후, 남아 있는 모든 수를 출력한다.
- 시간 복잡도는 O(N^2) 정도로 판단, 일반적으로는 O(nlog(logn))이다.
📌 문제 037) 소수 구하기
시간 제한 2초, 실버 III, 백준 1929번
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
3 16
출력
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
3 5 7 11 13
1단계 문제 분석
- 숫자 사이에 소수를 출력해야 한다.
- N의 최대 범위가 1,000,000이므로 일반적인 소수 구하기 방식으로 문제를 풀면 시간 초과가 발생한다.
- 에라토스테네스 방법으로 풀어보자.
- 크기가 N+1인 리스트를 선언한 후, 값은 각각의 인덱스값으로 채운다. 0은 사용하지 않으니 0번째 배열은 생략한다.
- 1은 소수가 아니므로 삭제한다.
- 2부터 N의 제곱근까지 값을 탐색한다. 값이 인덱스값이면 그대로 두고, 그 값의 배수를 탐색해 0으로 변경한다.
- 배열에 남아 있는 수 중 M 이상 N 이하의 수를 모두 출력한다.
2단계 슈도 코드
M(시작 수) N(종료 수)
A(소수 리스트)
for N만큼 반복:
A 리스트 초기화 # 각각의 인덱스값으로 초기화
for N의 제곱근까지 반복:
소수가 아니면 넘어감
for 소수의 배수 값을 N까지 반복:
현재 수가 소수가 아니라는 것을 표시
for M~N까지 반복:
A에서 소수인 값 출력3단계 코드 구현
import math
M, N = map(int, input().split())
A = [0] * (N+1)
for i in range(2, N+1):
A[i] = i
for i in range(2, int(math.sqrt(N)) + 1): # 제곱근까지만 수행
if A[i] == 0:
continue
for j in range(i+i, N+1, i): # 배수 지우기
# i+i는 i의 배수, i+i부터 N까지의 범위에서 i간격으로 i의 배수를 선택
A[j] = 0
for i in range(M, N+1):
if A[i] != 0:
print(A[i])📌 문제 038) 거의 소수 구하기
시간 제한 2초, 실버 I, 백준 1456번
어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다.
두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.
입력
첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다.
1 1000 # A, B
출력
첫째 줄에 총 몇 개가 있는지 출력한다.
25
1단계 문제 분석
- 최대 범위에 해당하는 모든 소수를 구해 놓고, 이 소수들의 N제곱값이 입력된 A와 B사이에 존재하는지 판단해 문제를 해결할 수 있다.
- 입력에서 주어진 범위의 최댓값 10^14의 제곱근인 10^7까지 소수를 탐색해야 한다.
- 에라토스테네스의 체를 이용해 빠르게 소수를 먼저 구한다.
- 그 이후 주어진 소수들의 N제곱값이 A~B 범위 안에 존재하는지 판별해 유효한 소수의 개수를 세면 이 문제를 해결할 수 있다.
- 2~10,000,000 사이에 존재하는 모든 소수를 구한다.
- 각각의 소수에 관해 소수를 N제곱한 값이 B보다 커질 때까지 반복문을 실행한다. 이때 소수를 N제곱한 값이 A보다 크거나 같으면 거의 소수로 판단해 카운트한다. 모든 소수에 관해서는 반복문을 실행한 후 카운트한 값을 출력한다.
- 이 부분을 실제 구현하면 N제곱한 값을 구하는 도중 값이 변수 표현 범위를 초과하는 경우가 발생한다. 따라서 계산 오류를 방지하려면 N^k과 B값이 아니라 N과 B/N^(k-1)을 비교하는 형식으로 정리해야 한다.
2단계 슈도 코드
Min(시작 수) Max(종료 수)
A(소수 리스트)
for 2~10000000: # 10^14의 제곱근인 10^7까지 반복
A 리스트 초기화 # 각각의 인덱스값으로 초기화
for 10000000의 제곱근까지 반복: # 에라토스테네스의 체
소수가 아니면 넘어감
for 소수의 배숫값을 10000000까지 반복:
현재 수가 소수가 아니라는 것을 표시
for 2~10000000:
A 리스트에서 소수인 값일 때
temp = 현재 소수
# 변수 표현 범위를 넘어갈 수 있어 이항 정리로 처리
while 현재 소수 <= Max/temp:
if 현재 소수 >= Min/temp: 정답값 증가
temp = temp * A[i]
정답 출력3단계 코드 구현
import math
Min, Max = map(int, input().split())
A = [0] * (10000001)
for i in range(2, len(A)):
A[i] = i
for i in range(2, int(math.sqrt(len(A)) + 1)): # 제곱근까지만 수행
if A[i] == 0:
continue
for j in range(i + i, len(A), i): # 배수 지우기
A[j] = 0
count = 0
for i in range(2, 10000001):
if A[i] != 0:
temp = A[i]
while A[i] <= Max/temp:
if A[i] >= Min/temp:
count += 1
temp = temp * A[i]
print(count)
안녕하세요 :)