단계별로 풀어보기(92)
-
백준 4938 파이썬 에라토스테네스의 체
백준 4938 - 베르트랑 공준문제https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼www.acmicpc.net답안 코드 :while True: n = int(input()) if n == 0: break # 에라토스테네스의 체를 활용한 소수 판별 is_prime = [True] * (2 * n + 1) is_prime[0] = is_prime[1] = False # 0과 1은 소수가 아님 for i in range(..
2024.04.27 -
백준 1929 파이썬 에라토스테네스의 체
백준 1929 - 소수 구하기문제https://www.acmicpc.net/problem/1929 1929번: 소수 구하기첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.www.acmicpc.net답안 코드 :# 에라토스테네스의 체# 입력 받기m, n = map(int, input().split())# 소수를 저장하는 리스트primes = []# 2부터 n까지의 수를 모두 소수라 가정하고 시작is_prime = [True] * (n + 1)is_prime[0] = is_prime[1] = False # 0과 1은 소수가 아님# 에라토스테네스의 체 알고리즘for i in range(2, int(..
2024.04.26 -
백준 4134 파이썬
백준 4134 - 다음 소수문제https://www.acmicpc.net/problem/4134 4134번: 다음 소수정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오.www.acmicpc.net답안 코드 :import math# 소수 판별 함수def is_prime(num): if num 백준 / 문제 / 단계별로 풀어보기 / 15단계 약수, 배수와 소수 2생각 :# √N까지만 나눠서 소수를 판별하는 문제 # n부터 시작해서 하나씩 증가시키면서 소수인지를 판별하고, # 소수일 경우 해당 값을 출력하고 반복문을 종료 # 브루트포스로 소수를 찾기
2024.04.25 -
백준 1735 파이썬
백준 1735 - 분수 합 문제 https://www.acmicpc.net/problem/1735 1735번: 분수 합 첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. www.acmicpc.net 답안 코드 : def gcd(a, b): # 최대공약수, 유클리드 호제 while b: a, b = b, a % b return a A, B = map(int, input().split()) C, D = map(int, input().split()) N = gcd(A * D + C * B, B * D) print((A * D + C * B) // N, B * D // N) 백준 / 문제 / 단계별로 풀어보기 / 15단..
2024.04.24 -
백준 13241 파이썬 유클리드 호제법
백준 13241 - 최소공배수 문제 https://www.acmicpc.net/problem/13241 13241번: 최소공배수 정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다. 예: 10은 5의 배수이다 (5*2 = 10) 10은 10의 배수이다(10*1 = 10) 6은 1의 배수이다(1*6 = 6) 20은 1, 2, 4,5,10,20의 배수이다. 다 www.acmicpc.net 답안 코드 : def gcd(a, b): while b: a, b = b, a % b return a def lcm(a, b): return a * b // gcd(a, b) A, B = map(int, input().split()) result = lcm(A, B) print(resul..
2024.04.23 -
백준 1934 파이썬 gcd와 lcm
백준 1934 - 최소공배수 문제 https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 답안 코드 : import math # 최소공배수 계산하는 함수 def lcm(a, b): return a * b // math.gcd(a, b) T = int(input()) # 각 테스트 케이스에 대해 최소공배수 계산 및 출력 for _ in range(T): A, B = map(int, input().split()) result = lcm..
2024.04.22