소수(15)
-
백준 2501번 파이썬
백준 2501 : 약수 구하기 문제 https://www.acmicpc.net/problem/2501 2501번: 약수 구하기 첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다. www.acmicpc.net 답안 코드 : N, K = map(int, input().split()) List = [] for i in range(1, N + 1): if N % i == 0: List.append(i) if len(List) < K: print(0) else: print(List[K - 1]) 백준 / 문제 / 단계별로 풀어보기 / 9단계 약수, 배수와 소수 생각 : print(List[K - 1]) # 인덱스 번호에 맞춰서 K-1번째로 해야함
2024.03.06 -
백준 5086 파이썬
백준 5086 파이썬 : 배수와 약수 문제 https://www.acmicpc.net/problem/5086 5086번: 배수와 약수 각 테스트 케이스마다 첫 번째 숫자가 두 번째 숫자의 약수라면 factor를, 배수라면 multiple을, 둘 다 아니라면 neither를 출력한다. www.acmicpc.net 답안 코드 : while 1: x, y = map(int, input().split()) if x == 0 and y == 0: break if x y and x % y == 0: print("multiple") else: print("neither") 백준 / 문제 / 단계별로 풀어보기 / 9단계 약수, 배수와 소수..
2024.03.05 -
정수론 : 소수 구하기 에라토스테네스의 채
소수 소수 구하기의 핵심 이론 소수를 구하는 대표적인 판별법으로는 에라토스테네스의 체를 들 수 있다. 에라토스테네스의 체 원리는 다음과 같다. ① 구하고자 하는 소수의 범위만큼 1차원 리스트를 생성한다. ② 2부터 시작하고 현재 숫자가 지워진 상태가 아닌 경우 현재 선택된 숫자의 배수에 해당하는 수를 리스트에서 끝까지 탐색하면서 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다. ③ 리스트의 끝까지 ②를 반복한 후 리스트에서 남아 있는 모든 수를 출력한다. 에라토스테네스의 체를 사용할 때 시간 복잡도 일반적으로 에라토스테네스의 체를 구현하려면 이중 for문을 이용하므로 시간 복잡도가 O(N^2) 정도라고 판단할 수 있다. 하지만 실제 시간 복잡도는 최적화의 정도에 따라 다르겠지만, 일반적으로 O(Nlo..
2024.02.16