정수론 36

백준(Python) 2960번 에라토스테네스의 체 풀이

Python으로 구현한 2960번 에라토스테네스의 체 문제 풀이입니다. https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net n, k = map(int, input().split()) data = [True for i in range(n + 1)] count = 0 for i in range(2, len(data) + 1) : for j in range(i, n+1, i) : if data[j] : data[j] = False count += 1 if count == k : print(j) break 초기에 n개의 data 리스트의 값들..

백준(Python) 10610번 30 풀이

Python으로 구현한 10610번 30 문제 풀이입니다. https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net n = list(input()) n.sort(reverse = True) sum = 0 for i in n : sum += int(i) if sum % 3 != 0 or "0" not in n : print(-1) else : print(''.join(n)) 이 문제는 30의 배수가 되는 가장 큰 수를 구하는 문제로, 30의 배수가 되려면 ..

백준(Python) 6588번 골드바흐의 추측 풀이

Python으로 구현한 6588번 골드바흐의 추측 문제 풀이입니다. https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net import sys num = 1000001 data = [True for _ in range(num)] for i in range(2, int((num-1)**0.5) + 1) : if data[i] : for j in range(i + i, num, i) : data[j] = False while Tru..

백준(Python) 1476번 날짜 계산 풀이

Python으로 구현한 1476번 날짜 계산 문제 풀이입니다. https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net e, s, m = map(int, input().split()) a, b, c = 1, 1, 1 count = 0 while True : count += 1 if e==a and s==b and m==c : break a += 1 b += 1 c += 1 if a == 16 : a = 1 if b == 29 : b = 1 if c == 20..

백준(Python) 1037번 약수 풀이

Python으로 구현한 1037번 약수 문제 풀이입니다. https://www.acmicpc.net/problem/1037 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net n = int(input()) data = list(map(int, input().split())) max_value = max(data) min_value = min(data) print(max_value * min_value) 입력받은 리스트는 모두 진짜 약수이기 때문에 값들 중 최솟값과 최댓값을 구하여 두 수의 곱을 출력한다.

백준(Python) 4948번 베르트랑 공준 풀이

Python으로 구현한 4948번 베르트랑 공준 문제 풀이입니다. https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net from math import sqrt while True : n = int(input()) if n == 0 : break result = 0 for i in range(n+1, 2*n + 1) : if i == 1 : continue elif i == 2 : result += 1 continue else : for j i..

백준(Python) 1934번 최소공배수 풀이

Python으로 구현한 1934번 최소공배수 문제 풀이입니다. https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net tc = int(input()) for _ in range(tc) : a, b = map(int, input().split()) a_value, b_value = a, b while b_value != 0 : a_value = a_value % b_value a_value, b_value = b_value, a_va..

백준(Python) 11653번 소인수분해 풀이

Python으로 구현한 11653번 소인수분해 문제 풀이입니다. https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net n = int(input()) count = 2 while n != 1 : if n % count == 0 : print(count) n //= count else : count += 1 소인수분해는 기본적으로 2부터 진행하기 때문에 변수 number에 2를 할당한다. while문을 통해 반복실행하고, 그 내부에서는 조건문을 통해 입력받은 n을 number 값으로 나눈 나머지 값이 0이라면 number 값을 출력한다. 또한, 변수 n에 number로 나..

백준(Python) 2581번 소수 풀이

Python으로 구현한 2581번 소수 문제 풀이입니다. https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net m = int(input()) n = int(input()) result = 0 min = 0 for i in range(m, n + 1) : flag = 0 if i == 1 : continue for j in range(2, i) : if i % j == 0 : flag = 1 break if flag == 0 : if min == 0 : min ..

백준(Python) 2609번 최대공약수와 최소공배수 풀이

Python으로 구현한 2609번 최대공약수와 최소공배수 문제 풀이입니다. https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net a, b = map(int, input().split()) a_value = a b_value = b while b_value != 0 : a_value = a_value % b_value a_value, b_value = b_value, a_value print(a_value) print(a * b // a_value) 반복문을 통해 최대공약수를 먼저 구하도록 한다. 두 수 a와 b가 있..