행복한 개구리

def IsPrime(n): seive = [True] * n for i in range(2, int((n ** 0.5) + 1)): if seive[i] == True: for j in range(i + i, n, i): seive[j] = False return [i for i in range(2, n) if seive[i] == True] listPrimeNumbers = IsPrime(123456 * 2) while True: M = int(input()) if M == 0: break result = [] for i in listPrimeNumbers: if M < i

import sys M, N = map(int, sys.stdin.readline().split()) pn = [] for i in range(M, N+1): if i == 1: pass elif i == 2: pn.append(i) else: for j in range(2, i): if i % j == 0: break elif j == i - 1: pn.append(i) for _ in pn: print(_) 위와 같은 코드 또는 조금 더 정리된 코드로 작성해도 시간 초과가 나왔습니다. 그래서 검색을 해보니 "에라토스테네스의 체"를 사용해야 한다는데 무엇인지 찾아보았습니다. 에라토스테네스의 체 수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘..

N = int(input()) while N > 1: for i in range(2, N+1): if N % i == 0: N = int(N/i) print(i) break 작은 약수부터 출력하는 방식입니다. 입력받은 N을 작은 수부터 반복하여 약수를 찾아내고, N을 약수로 나누어 다시 반복문을 돌려 약수를 구합니다. N이 1이 되면 약수는 1밖에 없기 때문에 반복은 N이 1을 초과할 때만 실행되게 짜줍니다.

m = int(input()) n = int(input()) result = [] for i in range(m, n+1): div = 0 if i > 1: for j in range(2, i): if i % j == 0: div += 1 break if div == 0: result.append(i) if len(result) == 0: print(-1) else: print(sum(result)) print(min(result)) 중첩반복문을 실행하여 주어진 두 수사이의 각 숫자들이 소수인지 아닌지 증명합니다. 약수를 구하는 범위가 2부터 n-1까지 이기때문에 소수라면 약수가 존재하지 않을테니 result리스트에 append메서드를 사용하여 요소를 추가해줍니다. 약수가 발견된다면 break으로 반복문..

n = int(input()) nums = list(map(int, input().split())) cnt = 0 for i in nums: div = 0 if i == 1: continue else: for j in range(2, i): if i % j == 0: div += 1 if div ==0: cnt += 1 print(cnt) 소수는 약수가 자신 또는 1밖에 없는 수를 말합니다. 따라서 1을 제외하고 주어진 수 ~ 주어진 수 -1까지의 수로 나눌 수 없을 때 소수임을 증명할 수 있습니다. 그러므로 1을 continue하여 건너뛰고 2부터 i-1 까지의 수로 나누어 봅니다. 만약 소수가 아니라면 div의 값이 1씩 올라가기 때문에 소수가 아니라는 뜻이 됩니다. => 따라서 중첩 반복문이 끝나고..

import math T = int(input()) for _ in range(T): x, y = map(int, input().split()) distance = y - x if distance < 3: print(distance) else: root = math.ceil(math.sqrt(distance)) if distance