just inside

문제 링크https://www.acmicpc.net/problem/2609문제 설명 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.  입력 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.  출력 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. 제출 코드import sysinput = sys.stdin.readlinedef gcd(a, b): while b != 0: a, b = b, a % b return a def lcd(a, b): return abs(a*b) // gcd(a, b)a, b = map..

유클리드 호제법 (Euclidean Algorithm) / 최대공약수 계산두 정수의 최대공약수 (GCD, Greatest Common Divisor)를 효율적으로 계산하는 알고리즘두 수의 최대공약수가 두 수의 차이의 최대공약수와 같다는 것원리두 정수 $a$와 $b$ $(a>b)$의 최대공약수를 구하기 위해 다음 과정을 반복$a$를 $b$로 나눈 나머지 $r$을 구한다.$a$를 $b$로, $b$를 $r$로 대체한다.$r$이 0이 될 때까지 이 과정을 반복한다.$r$이 0이 되었을 때, $b$가 $a$와 $b$의 최대공약수$$ GCD(a,b)=GCD(b,a\bmod b)$$def gcd(a,b): while b != 0: a, b = b, a % b return a시간복잡도는 $O(log\ min(a..

문제 링크https://www.acmicpc.net/problem/1929문제 설명 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.  입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.  출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 제출 코드import sysimport mathinput = sys.stdin.readlinem, n = map(int, input().split())nums = [True]*(n+1)for i in range(2, int(math.sqrt(n))+1): if nums[i]: for j in range(i*i, n+1,..

문제 링크https://www.acmicpc.net/problem/1987문제 설명주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 입력첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. 출력주어진 수들 중 소수의 개수를 출력한다.제출 코드import sysimport mathinput = sys.stdin.readlinen = int(input().rstrip())nums = list(map(int, input().split()))result = 0def isPrime(n): if n == 1: return False # 2부터 제곱근까지 모든 수 확인 for i in r..