15단계 문제들 2탄
인트로
에라토스테네스의 체의 늪에 빠져보시죠 😋
에라토스테네스 관련 설명
사실 위키백과에서 아~~주 잘 설명되어있슴 :>
1929번 - 소수 구하기
입력 받은 M과 N을 포함한 그 사이의 소수를 출력하면 됨
코드
def isprime(x):
if x == 0 or x == 1:
return False
for i in range(2, int(x**0.5)+1):
if x % i == 0:
return False
return True
start, end = map(int,input().split())
for n in range(start,end+1,1):
if n == 1:
n += 1
else:
if isprime(n):
print(n)for문으로 입력 받은 값만큼 들어가면서 해당 값이 소수이면 출력해주면 됨
4948번 - 베르트랑 공준
0을 받을 때까지 반복하고, 입력 받은 값보다 크고 입력 받은 값의 2배를 포함하는 값까지
소수의 개수가 몇 개인지 출력하면 됨.
코드
import math
n = 123456
eratos = [1] * (2 * n + 1)
eratos[0] = 0
eratos[1] = 0
for i in range(2, int(math.sqrt(len(eratos)))):
if eratos[i]:
for j in range(i+i, len(eratos), i):
eratos[j] = 0
while (True):
N = int(input())
if N == 0:
break
else:
print(sum(eratos[N+1:(2*N)+1]))이 문제의 중요한 부분은 n의 최댓값이 123,456인데 시간제한이 1초이다.
따라서, 매번 소수를 계산하면 시간초과에 걸린다.
어떻게 아냐구요? 저도 알고싶지 않았는ㄷ..
그래서 처음에는 에라토스테네스의 체를 이용하여 최댓값만큼 소수를 구해버린다!
2n까지 구해야 함으로 최댓값의 2배만큼의 크기로 소수를 미리 구해버린다.
그런 다음, 주어진 입력 값의 범위만큼 slice한 한 다음 더해준다.
위에서 우리는 소수인 값들을 1로 지정했다.
따라서 해당 인덱스만큼 잘라서 합을 구해버리면 그만큼의 개수의 소수를 가진다고 해석할 수 있다.
17103번 - 골드바흐 파티션
코드
import math
from itertools import combinations
T = int(input())
inputs = []
for _ in range(T):
inputs.append(int(input()))
maxinput = max(inputs)
eratos = [1] * (maxinput + 1)
eratos[0] = 0
eratos[1] = 0
for i in range(2, int(math.sqrt(maxinput)) + 1):
if eratos[i]:
for j in range(i * i, maxinput + 1, i):
eratos[j] = 0
for i in range(T):
count = 0
n = inputs[i]
for j in range(2, n // 2 + 1):
if eratos[j] and eratos[n - j]:
count += 1
print(count)이것도 시간초과를 막기 위해서 입력 받은 값들 중에 가장 큰 값으로 미리 소수리스트를 만들어 놓았다.
마지막 for문이 가장 중요한 실행문인데,
입력 값을 2부터 입력값의 절반값까지 돌려본다.
예를 들어 6인 경우 1 5, 2 4, 3 3 까지를 제외하고는 동일한 쌍이 될 수 있으므로
n//2 (반까지 포함) 돌린다. 돌리는 과정에서 소수인지 확인한다.
만약 둘 다 소수인 것이 판별되면 카운트 해준다.
13909번 - 창문 닫기
1번은 1의 배수만큼의 창문을 열고,
2번은 2의 배수만큼의 창문을 닫고,
3번은 3의 배수만큼의 창문을 열고..
이런식으로 N번까지의 학생이 진행하는 것이다.
이렇게 진행했을 때 마지막으로 열려있는 창문의 개수를 세는 것이다.
첫 코드 - 메모리 초과 (틀림)
T = int(input())
eratos = [0] * (T+1)
for i in range(1, T+1):
for j in range(i, T+1, i):
if eratos[j] == 0:
eratos[j] = 1
else:
eratos[j] = 0
print(eratos.count(1))처음에는 나도 1번이 열고, 2번이 닫고, 3번이 열고..
이런식의 구현을 해봤다. 그러다보니 계속 시간초과 / 메모리 초과가 났다.
그래서 N = 10으로 가정하고 직접 손으로 풀어보았다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 1번학생 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2번학생 | 1 | 1 | 1 | 1 | 1 | |||||
| 3번학생 | 1 | 1 | 1 | |||||||
| 4번학생 | 1 | 1 | ||||||||
| 5번학생 | 1 | 1 | ||||||||
| 6번학생 | 1 | |||||||||
| 7번학생 | 1 |
| 결과 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
이렇게 되어 1,4,9번만 열려지게 된다.
직접 세어보면 열고 - 닫고 가 됨으로 1의 값이 짝수가 되면 닫혀지는 것을 알 수 있다.
하지만 더 나아가보면, 1 4 9는 10이하의 제곱수라는 것을 알게 되었다.
따라서, 이 방법으로 입력된 값의 제곱수의 개수만 알면 되었다.
여기서 한번 더 생각해보았다. 10이하의 제곱수는 결국 10의 제곱수의 정수부분이라는 것을 알게 되었다.
즉 루트10 은 3..xx 이므로 3만이 나오게 됨으로 정답이 될 수 있다는 것이다.
따라서, 수정한 코드는
print(int(int(input())**(0.5)))이 코드가 맞고 나서 숏코딩 제출을 보니까 다 이 코드였다는 것을 알게 되었다 🤣😂
후기
소수 정복 완료!
