[백준/python] 기본 수학 2 전체 풀이(8단계)

 

목차

 

소수 찾기(#1978)

• Problem

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

 

• Hint

소수의 특징을 생각해보면 n으로 나누었을때(1과 자신을 제외한) 나누어 떨어지면 안된다.

 

• Solution

n = int(input())
r=0
for i in map(int,input().split()):
    c=1
    for j in range(i-2):
        if i%(j+2)==0:
            c=0
    if i==1:
        r-=1
    r+=c
print(r)

1로 나누었을때도 나누어 떨어진다고 인식하기 때문에 나누는 인자를 2부터 시작하게 코딩하였다.

---

 

소수(#2581)

• Problem

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

 

• Hint

소수의 특징을 잘 생각해보자

 

• Solution

count를 이용한 풀이

a=int(input())
b=int(input())
r=[]
for i in range(a,b+1):
    c=0
    for j in range(1,i+1):
        if i%j==0:
            c+=1
    if c==2:
        r.append(i)
if len(r)==0:
    print('-1')
else:
    print(sum(r))
    print(r[0])

count 변수 (c) 를 이용하여 나누어 떨어지는 경우가 발생하는 경우 +=1을 통해 소수의 정의(1과 자기 자신)에 부합하게 하였고 2개가 아닐 시에 result 리스트에 추가 되지 않게 하였다.

range(1,i+1) 을 이용하여 떨어지는 개수가 2개 일 경우 추가를 한다 라는 기본 개념을 사용했다

보통 소수를 다루는 알고리즘은 n이 소수인지를 판별할 당시에 n까지 확인 하는 것이 아니라 n의 제곱근 까지만 확인해보면 나누어 떨어지는 경우 2번째의 약수와 n-2 번째의 약수의 곱은 n과 같기 때문에 제곱근까지만 확인을 해봐도 된다. 

---

 

소인수분해(#11653)

• Problem

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

 

• Hint

출력이 작은수에서 큰 수로 소인수가 모두 표시 되어지고 있다. 소인수의 정의를 생각해보자

 

• Solution

a=int(input())
for i in range(a-1):
    i=i+2
    while a%i==0:
        a=a//i
        print(i)

1은 항상 인수로 갖으니 2부터 n 까지의 반복문 속에서 나누어 떨어지는 값을 출력하는 방식을 세웠다.

---

 

소수 구하기(#1929)

• Problem

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

 

• Hint

제곱근까지만 확인해보기, 에라토스테네스의 체 사용해보기

 

• Solution

에라토스테네스의 체를 이용한 풀이

a,b = map(int,input().split())

def sieve(n):
    c=[True]*(n+1)
    na=int(n**0.5)
    for i in range(2,na+1):
        if c[i]==True:
            for j in range(i+i, n+1, i):
                c[j]=False
    return[i for i in range(2,n+1) if c[i]==True]

result = sorted(set(sieve(b))-set(sieve(a-1)))
print(*result,sep='\n')

리스트를 만들되, 리스트의 번호를 바로 출력해주고 싶어서 n+1 개의 리스트를 만들어 주었다.

na 에 n의 제곱근 값을 담고 모두를 소수라고 가정한 뒤에

2의 배수를 전부 소수가 아니라고(0)으로 지정한다.

3의 배수를 ...

4는 이미 소수가 아니다 (2에 의해)

5의 배수를 ...

6은 이미 소수가 아니다 (2에 의해)

....

이런 방식으로 제곱근까지만 진행하여준다.

 

이러한 방식이 에라토스테네스의 체 원리이다.

---

제곱근 까지만 확인하는 방법을 이용한 풀이

def isPrime(num):
    if num==1:
        return False
    else:
        for i in range(2, int(num**0.5)+1):
            if num%i == 0:
                return False
        return True

m,n = map(int, input().split())

for i in range(m,n+1):
    if isPrime(i):
        print(i)

제곱근까지만 확인하며 소수를 출력하는 방식이다.

 

시간복잡도 /포스팅예정

 

베르트랑 공준(#4948)

• Problem

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.

 

• Hint

문제의 조건을 잘 읽자..

 

• Solution

을 이용한 풀이

def sieve(n):
    c=[True]*(n+1)
    na=int(n**0.5)
    for i in range(2,na+1):
        if c[i]==True:
            for j in range(i+i, n+1, i):
                c[j]=False
    return[i for i in range(2,n+1) if c[i]==True]

for k in [*open(0)][:-1]:
    k=int(k)
    result = sorted(set(sieve(2*k))-set(sieve(k)))
    print(len(result))

체를 이용하여 풀었다. k를 정수형으로 바꾸어 주었고 k 보다 크고 2k 보다 작거나 같은 소수 이므로 result 내의 함수를 저렇게 바꾸어주었다.

---

숏코딩

while n:=int(input()):
    p=(2*n+1)*[1]
    i=1
    while i<n:
        i+=1
        p[2*i::i]=(2*n//i-1)*[0]
        print(sum(p[n+1:]))

최소한의 자원만을 사용하려는... 아름다운 코드인 것 같다 이런식으로도 코드의 단축이 가능하구나 라고 느끼게 되는 코드

 

골드바흐의 추측(#9020)

• Problem

1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다. 골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다. 2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

 

• Hint

10000보다 작으니 미리 10000이하의 소수들의 리스트를 뽑아낸 후에 생각해보자

두 정수의 차이가 작은 한 쌍만 출력을 해야한다. 그 쌍을 구하려면 굳이 1에서 부터 n까지 반복문을 돌려야할까?

 

• Solution

break 을 이용한 풀이

c=[True]*(10000+1)
na=int(101)
for i in range(2,na):
    if c[i]==True:
        for j in range(i+i, 10001, i):
            c[j]=False
res=[i for i in range(2,10001) if c[i]==True]
r=[]
for k in [*open(0)][1:]:
    k=int(k)
    A=k/2
    while 1:
        if A in res and k-A in res:
            print(int(A), int(k-A)) 
            break
        else:
            A-=1

맞는 쌍을 찾았을때 break 를 통하여 반복문을 멈추게 하였다.

 

10000까지의 리스트를 먼저 산출해내고 계산을 하게 하는건 생각하지 못하였다. 코딩테스트나 알고리즘 방식에 적응할 필요가 있는것 같다.