/ PROGRAMING

백준-단계별-기본 수학 2단계

백준-단계별-기본 수학 2단계

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

기억해야하는 부분

  • 소수 확인 범위는 해당 숫자의 제곱근까지 나누어보면 된다.( 효율적 )
  • 소인수분해 부분에서 같은 숫자로 나누어지지 않을 때까지 하는 것이 핵심, 사람이 하는 것처럼

소수 찾기 (1-1978)

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

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

  • 입력
    첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

  • 출력
    주어진 수들 중 소수의 개수를 출력한다.

  • 예제 입력 1
    4
    1 3 5 7
  • 예제 출력 1
    3
def Check_prime_number(num):
    if num <= 1 : return 0 # 1 보다 큰 수 
    # 소수란 1보다 큰 자연수 중 약수가 1과 자신인 것
    half_num = num/2 # 본인의 반 안에 약수가 존재하으로 2로 나눈다.
    half_num = int(half_num if half_num == int(half_num) else half_num+1) # 올림

    for i in range(2,half_num+1): # half_num 본인도 포함해야 한다.
        if not num%i: # 나누어 떨어지면 0 이므로 False
            return 0
    return 1 # 소수

for i in range(1, 100):
    if Check_prime_number(i):
        print(i, end = " ")
        

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

# 제출코드 
def Check_prime_number(num):
    if num <= 1 : return 0 # 1과 2를 제외한 짝수 제외
    # 소수란 1보다 큰 자연수 중 약수가 1과 자신인 것
    half_num = num/2 # 본인의 반 안에 약수가 존재하으로 2로 나눈다.
    half_num = int(half_num if half_num == int(half_num) else half_num+1) # 올림

    for i in range(2,half_num+1): # half_num 본인도 포함해야 한다.
        if not num%i:# 나누어 떨어지면 0 이므로 False
            return 0
    return 1

repeat_num = int(input())
prime_count = 0
INPUT_INT_list = [int(x) for x in input().split()] # map(int, input().split()) 같은 의미
for i in range(repeat_num):
    prime_count += Check_prime_number(INPUT_INT_list[i])
print(prime_count)

 4
 1 3 5 7


3

소수 (2-2581)

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

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

  • 입력
    입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.
    M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

  • 출력
    M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.
    단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

  • 예제 입력 1
    60
    100
  • 예제 출력 1
    620
    61
  • 예제 입력 2
    64
    65

  • 예제 출력 2
    -1

  • 나만의 해석
    • 앞 선 문제인 소수 찾기 (1-1978)에서 만든 함수를 이용한다.
    • 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. 해당 문구에 대한 조건문을 꼭 넣어준다.
# 제출코드 
def Check_prime_number(num):
    if num <= 1 : return 0 # 1과 2를 제외한 짝수 제외
    # 소수란 1보다 큰 자연수 중 약수가 1과 자신인 것
    half_num = num/2 # 본인의 반 안에 약수가 존재하으로 2로 나눈다.
    half_num = int(half_num if half_num == int(half_num) else half_num+1) # 올림

    for i in range(2,half_num+1): # half_num 본인도 포함해야 한다.
        if not num%i:# 나누어 떨어지면 0 이므로 False
            return 0
    return 1

M = int(input())
N = int(input())

prime_list = []

for i in range(M,N+1):
    if Check_prime_number(i) == 1:
        prime_list.append(i)
        
if len(prime_list) == 0 : print(-1)
else:
    print(sum(prime_list))
    print(min(prime_list))


 60
 100


620
61

소인수분해 (3-11653)

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

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

  • 입력
    첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

  • 출력
    N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

  • 예제 입력 1
    72
  • 예제 출력 1
    2
    2
    2
    3
    3
  • 예제 입력 2
    3
  • 예제 출력 2
    3
  • 예제 입력 3
    6
  • 예제 출력 3
    2
    3
  • 예제 입력 4
    2
  • 예제 출력 4
    2
  • 예제 입력 5
    9991

  • 예제 출력 5
    97
    103

  • 나만의 해석
    • 입력된 수보다 2부터 1/2 작은 상태일 때까지 나누어지지 않으면 끝이 난다.
    • 작은 숫자부터 높여가며 나누어지지 않을때까지 while 문을 통해 반복해 진행한다.
#N = int(input())
N = 72

M = 2 # 나눌 수

while N != 1: # 입력값이 1이 될 때까지 아래와 같은 과정을 반복한다.
    if N % M == 0 : # 나누어떨어지면
        print(M) # 나누어떨어지는 수는 소수인 인수이다.
        N = N // M # M 으로 나눈 몫을 저장하여 N이 1이 될때까지 반복한다.
    else:
        M += 1 # M으로 나누어지지 않는다면 1 증가하여 나눈다.

2
2
2
3
3

소수 구하기 (4-1929)

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

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

  • 입력
    첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

  • 출력
    한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

  • 예제 입력 1
    3 16

  • 예제 출력 1
    3
    5
    7
    11
    13

  • 나만의 해석
    • 반복해서 직접 구하는 코드는 시간초과가 발생하므로 최소한으로 확인하는 코드로 작성해야한다.
    • 핵심!!! 소수구하기의 범위는 해당 수의 제곱근 범위까지만 나누어 확인해주면 된다. 그러면 계산 양이 확 줄어든다.
# 제출코드 
#M,N = map(int,input().split())
M = 3
N = 16

def isPrime(num):
    if num == 1 : return False # 1이면 소수가 아니므로 Fasle 출력한다.
    
    Last_num = int(num**(1/2))
    
    for i in range(2,Last_num+1):
        if num % i == 0:
            return False
    return True

for i in range(M,N+1):
    if isPrime(i):
        print(i)


3
5
7
11
13

베르트랑 공준 (5-4948)

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

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

  • 입력
    입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.
    입력의 마지막에는 0이 주어진다.

  • 출력
    각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

  • 제한
    1 ≤ n ≤ 123,456

  • 예제 입력 1
    1
    10
    13
    100
    1000
    10000
    100000
    0

  • 예제 출력 1
    1
    4
    3
    21
    135
    1033
    8392

  • 주의 깊게 봐야하는 것

    • 0이 되면 종료
    • n 초과 2n 이하
def isPrime(num):
    if num == 1 : return False # 1이면 소수가 아니므로 Fasle 출력한다.
    
    Last_num = int(num**(1/2))
    
    for i in range(2,Last_num+1):
        if num % i == 0:
            return False
    return True

n = int(input())
#n = 1

while n != 0:
    count_prime = 0
    for i in range(n+1,2*n+1):
        if isPrime(i):count_prime+=1
    print(count_prime)
    n = int(input())

 1


1


 10


4


 13


3


 100


21


 1000


135


 10000


1033


 100000


8392


 0
  • 시간초과로 인해 최대까지 소수를 미리 구하는 방법으로 최대한 반복을 제외하고 진행했다.
  • 미리 구하는 범위에서 소수는 n의 범위가 아닌 2*n 까지 구해주어야 한다.
# 제출코드 
def isPrime(num):
    if num == 1 : return False # 1이면 소수가 아니므로 Fasle 출력한다.
    
    Last_num = int(num**(1/2))
    
    for i in range(2,Last_num+1):
        if num % i == 0:
            return False
    return True

# 제한 1 ≤ n ≤ 123,456
prime_list = []
max_limit = 123456*2+1
for i in range(2,max_limit):
    if isPrime(i):
        prime_list.append(i)


while True:
    n = int(input())
    if n == 0 : break
    
    check_prime = [1 if x > n and x <= 2*n else 0 for x in prime_list]
    print(sum(check_prime))
  

 100000


8392


 0

골드바흐의 추측 (6-9020)

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

  • 문제
    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의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

  • 입력
    첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고 짝수 n이 주어진다.

  • 출력
    각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.

  • 제한
    4 ≤ n ≤ 10,000

  • 예제 입력 1
    3
    8
    10
    16

  • 예제 출력 1
    3 5
    5 5
    5 11

  • 중요한 부분

    • 2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성
    • 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력
def isPrime(num):
    if num == 1 : return False # 1이면 소수가 아니므로 Fasle 출력한다.
    
    Last_num = int(num**(1/2))
    
    for i in range(2,Last_num+1):
        if num % i == 0:
            return False
    return True


# 제한 4 ≤ n ≤ 10,000
prime_list = []
for i in range(2,10001):
    if isPrime(i):
        prime_list.append(i)

# T 입력, 테스트 개수
# T = int(input())
T = 3

# N = int(input())
N = 8
diff_min = 10000
goldbarh = []
for x in prime_list:
    for y in prime_list:
        diff_tmp = abs(x-y)
        if x+y == N and diff_min > diff_tmp :
            diff_min = diff_tmp
            goldbarh = [x,y]
            
print(*[x for x in goldbarh])

3 5

# 제출코드
def isPrime(num):
    if num == 1 : return False # 1이면 소수가 아니므로 Fasle 출력한다.
    
    Last_num = int(num**(1/2))
    
    for i in range(2,Last_num+1):
        if num % i == 0:
            return False
    return True


# 제한 4 ≤ n ≤ 10,000
prime_list = []
for i in range(2,10001):
    if isPrime(i):
        prime_list.append(i)

# T 입력, 테스트 개수
T = int(input())

for i in range(T):
    N = int(input())
    tmp_prime_list = [x for x in prime_list if x<=N]
    diff_min = 10000
    goldbarh = []
    for x in tmp_prime_list:
        for y in tmp_prime_list:
            diff_tmp = abs(x-y)
            if x+y == N and diff_min > diff_tmp :
                diff_min = diff_tmp
                goldbarh = [x,y]

    print(*[x for x in goldbarh])

 3
 8


3 5


 10


5 5


 16


5 11
  • 시간초과 발생
    • 소수 합을 구하는 과정이 T 만큼 반복돼서 생기는 문제인 것 같다.
    • T 시간동안 한번만 돌아가도 구할 수 있도록 dict 를 이용해본다.
# 제출코드
def isPrime(num):
    if num == 1 : return False # 1이면 소수가 아니므로 Fasle 출력한다.
    
    Last_num = int(num**(1/2))
    
    for i in range(2,Last_num+1):
        if num % i == 0:
            return False
    return True


# 제한 4 ≤ n ≤ 10,000
prime_list = []
for i in range(2,10001):
    if isPrime(i):
        prime_list.append(i)

# T 입력, 테스트 개수
T = int(input())
N = list()
for i in range(T):
    N.append(int(input()))
             
# result_list : 각 T의 diff_min 과 goldbarh를 저장하여 한번의 for문 반복으로 문제를 해결한다.
result_list = list()

for i in range(T):
    result_list.append({"diff_min":10000,"goldbarh":[]})


# 입력 받은 N의 값 중 최대로 소수 범위 조정             
prime_list = [x for x in prime_list if x<=max(N)]

for x in prime_list:

    for y in prime_list:
        diff_tmp = abs(x-y)

        for z in range(T):
            if x+y == N[z] and result_list[z]["diff_min"] > diff_tmp :
                result_list[z]["diff_min"] = diff_tmp
                result_list[z]["goldbarh"] = [x,y]

for i in result_list:
    print(*[x for x in i["goldbarh"]])

 3
 8
 10
 16


3 5
5 5
5 11
  • 시간초과 발생
    • 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력하는 것이면
      n/2 부터 내려가는 방법으로 찾고 찾으면 바로 출력하는 방법으로 비교 횟수를 줄여야겠다.
  • 추후 여러가지 시도 실패 후 구글링
    • 찾은 방법이 여러가지 있었지만 지금까지 해온 코드 방향과 가장 비슷한 코드 방법으로 가져왔다.
    • 신기한 방법으로는 에라토스테네스의 체 를 이용한 방법도 있었다.
  • 방법 설명
    • N/2 부분에서 좌우 +1,-1로 멀어지면서 소수인지 확인하면서 합이 맞으면 출력한다.
  • 기존 코드에 활용하는 방법
    • 결과 두개의 값은 N/2 와의 차이가 같으므로 인덱스를 하나씩 줄이고 늘리고 하면서 확인하면 괜찮을 것 같다.
# 제출코드
def isPrime(num):
    if num == 1 : return False # 1이면 소수가 아니므로 Fasle 출력한다.
    
    Last_num = int(num**(1/2))
    
    for i in range(2,Last_num+1):
        if num % i == 0:
            return False
    return True


# T 입력, 테스트 개수
T = int(input())

for i in range(T):
    N = int(input())
    
    half_N_a = half_N_b = N//2
    while True:
        if isPrime(half_N_a) and isPrime(half_N_b):
            print(half_N_a,half_N_b)
            break
        else:
            half_N_a-=1
            half_N_b+=1
        

 3
 8


3 5


 10


5 5


 16


5 11