[백준/Python]약수, 배수와 소수 2

문제

백준 - 약수, 배수와 소수 2

https://www.acmicpc.net/step/18

---

[4948]베르트랑 공준

문제링크: https://www.acmicpc.net/problem/4948

 

베르트랑 공준: 임의의 자연수 n에 대하여, n보다 크고 2n보다 작거나 같은 소수는 적어도 하나 존재한다.

 

문제를 그대로 읽어야 된다.

1. n보다는 (크고) 2n보다 (작거나 같아야 한다.)
2. n보다는 ((크고 2n보다 작거나) 같아야 한다.)

2번으로 생각하고 풀었는데 1번이었다.

즉 자연수 n이 주어졌을때 n < ... <= 2n를 만족하는 소수의 갯수를 구하면 된다.

 

풀이

전체풀이는 아래와 같다.

# 에라토스테네스의 체를 이용한 풀이.
from sys import stdin


input = stdin.readline

_max = 123456*2  # 체크범위가 n부터 2n까지이므로 max(123,456)의 두배만큼 만들어둬야함.
primes = [True] * (_max+1)
primes[0] = primes[1] = False

for i in range(2, int(_max**0.5)+1):
    if primes[i]:
        for j in range(i*i, _max+1, i):
            primes[j] = False

def check_primes(num):
    cnt = 0
    for i in range(num+1, 2*num+1):
        if primes[i]:
            cnt += 1
    return cnt

while True:
    n = int(input())
    if not n:
        break
    print(check_primes(n))

 

단계별 풀이

_max = 123456*2
primes = [True] * (_max+1)
primes[0] = primes[1] = False

우선 소수를 판별하는 범위가 "n초과 2n이하" 이므로, 리스트를 2n만큼 만들어준다.
0번째와 1번째는 False로 미리 설정해둔다.

 

for i in range(2, int(_max**0.5)+1):
    if primes[i]:
        for j in range(i*i, _max+1, i):
            primes[j] = False

그 다음 2부터 n의 제곱근까지 순회하며 i의 배수들을 제거한다.
소수만 남기는 과정이다.

 

+
i*2가 아닌 i*i부터 시작하는 이유?
: 사실 i*2로 해줘도 상관은 없다. 다만 i*2는 이전단계에서 처리되었을 가능성이 높기 때문에 i*i로 해줬다.
2*2 = 4, 2*3 = 6 ···, 3*2 = 6 => 이미 처리되었음. 3*3 = 9 ··· 이런식으로 흘러가기 때문임.

 

def check_primes(num):
    cnt = 0
    for i in range(num+1, 2*num+1):
        if primes[i]:
            cnt += 1
    return cnt

while True:
    n = int(input())
    if not n:
        break
    print(check_primes(n))

check_primes는 범위 내에 소수가 몇 개 있는지 체크하는 함수다.
답과 가장 직결되는 함수인 셈인데, n부터 2n까지 순회하며 primes[i]가 True인 갯수를 반환해준다.

 

그리고 while문을 통해 check_primes(입력값)을 반복한다.
입력값의 끝으로 0이 주어지므로 0이 되면 탈출.

---

[17103]골드바흐 파티션

문제링크: https://www.acmicpc.net/problem/17103

 

골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

 

맨 첫째줄엔 테스트의 개수 T가 주어지고, 둘째줄부터 짝수 N이 주어진다.
N이 몇개의 골드바흐 파티션을 가지고 있는지 알아내면 된다. 단, 중복은 불가능.

 

풀이

from sys import stdin


input = stdin.readline

def make_primes(limit) -> list:
    primes = [True] * (limit+1)
    primes[0] = primes[1] = False

    for i in range(2, int(limit**0.5)+1):
        if primes[i]:
            for j in range(i*i, limit+1, i):
                primes[j] = False
    return primes

primes = make_primes(1000000)

def check_primes(number):
    """
    checked를 없애는 대신 주어진 수의 절반만큼만 체크하기.
    어차피 i와 number-i 모두 체크하기때문에 실질적인 체크 범위는 같다.
    하지만 코드상의 범위는 수의 절반까지이므로 중복위험은 없음.
    """
    cnt = 0
    for i in range(2, number//2 + 1):
        if primes[i] and primes[number-i]:
                cnt += 1
    return cnt

T = int(input())
for _ in range(T):
    print(check_primes(int(input())))

 

단계별 풀이

def make_primes(limit) -> list:
    primes = [True] * (limit+1)
    primes[0] = primes[1] = False

    for i in range(2, int(limit**0.5)+1):
        if primes[i]:
            for j in range(i*i, limit+1, i):
                primes[j] = False
    return primes

primes = make_primes(1000000)

make_primes로 소수만 나타내는 리스트 primes를 생성해준다.
주어지는 정수 N의 범위는 2 <= N <= 1000000이므로 1000001개의 리스트가 만들어지는 셈이다.

 

def check_primes(number):
    cnt = 0
    for i in range(2, number//2 + 1):
        if primes[i] and primes[number-i]:
                cnt += 1
    return cnt

T = int(input())
for _ in range(T):
    print(check_primes(int(input())))

check_primes로 해당되는 소수의 갯수를 체크한다.
어떤 수 N = 합1 + 합2 일때, 합1 또는 합2는 무조건 N의 절반값 이하에 존재한다.
당연하다.

 

그러므로 2부터 N//2까지 primes를 체크하면 된다.

만약 i도 소수고, N-i도 소수라면 합1과 합2 모두 소수인 셈이므로 골드바흐 조건을 만족한다.

이 조건을 만족할때마다 cnt를 증가시켜주고, 순회가 끝나면 해당 cnt값을 반환한다.

위 과정을 T만큼 반복한다.

---

[13909]창문 닫기

문제링크: https://www.acmicpc.net/problem/13909

 

강의실에는 N개의 창문과 N개의 사람이 존재한다.
1부터 N까지, 각 수의 배수번째 창문이 열려있으면 닫고/닫혀있으면 연다.

예를 들어 현재 3개의 창문이 있고 3명의 사람이 있을 때,

1. 1번째 사람은 1의 배수인 1,2,3번 창문을 연다. (1, 1, 1)
2. 2번째 사람은 2의 배수인 2번 창문을 닫는다. (1, 0, 1)
3. 3번째 사람은 3의 배수인 3번 창문을 닫는다. (1, 0, 0)

마지막에 열려있는 창문의 갯수를 출력하는 문제다.

 

풀이

뭔가 꼼수가 존재할 것 같긴 했는데 안보였다ㅋㅋㅋ
그래서 곧이곧대로 풀어봤다.

# 첫번째 코드. 메모리 초과!
from sys import stdin


input = stdin.readline

N = int(input())

windows = [0] + [1]*N

for i in range(2, N+1):
    for j in range(i, N+1, i):
        if windows[j] == 1:
            windows[j] = 0
        else:
            windows[j] = 1

print(sum(windows))

0번째 창문은 평생 닫혀있을테니 0, 1번째부터 N번째까지는 1로 초기화해준다.
그리고 2부터 N까지 열려있으면 닫고, 닫혀있으면 열고, 열려있 닫, 닫 열, 열, 반복...

 

결과는 메모리 초과였다.

역시나 싶어 질문게시판을 둘러봤다.

허드슨님이 제시한 방법.
"1부터 16까지 시뮬레이션을 돌리면 규칙이 보일겁니다."

 

당장 실행해봤다.

from sys import stdin


input = stdin.readline

for N in range(1, 17):
    windows = [0] + [1]*N

    for i in range(2, N+1):
        for j in range(i, N+1, i):
            if windows[j] == 1:
                windows[j] = 0
            else:
                windows[j] = 1

    print(f"{N}의 합: {sum(windows)}, 배열:", *windows)

제곱근의 정수형이 답이었다.

 

진짜 풀이

from sys import stdin


input = stdin.readline

N = int(input())
print(int(N**0.5))

입력받은 수의 제곱근의 정수형이 답이었다.
너무 간단해서 허무하다.