yoo.dev

소수 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. (1과 본인 외의 약수가 없는 수) 가장 작은 소수는 2로, 유일한 짝수이다. 에라토스테네스의 체 (자연수 n까지의 소수 구하는 방법) 1. n+1개 크기의 배열 생성 후 True로 초기화 2. 최소 소수인 2부터 sqrt(n)까지 확인하면서 2-1. 소수인 경우(True), 본인보다 큰 (본인을 제외) 본인의 배수를 모두 False로 바꿔줌 3. 배열에서 소수인 애들의 인덱스를 0과 1을 제외하고 리턴 sqrt(n)까지만 확인하는 이유 n까지 해도 값의 차이는 없다. 다만, n을 소수에서 제외시킬 수 있는 약수는 sqrt(n)이하일 수 밖에 없기때문에 불필요한 연산을 없애 시간을 줄여준다. 예) n = 10 / n의 약수..

문제 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 풀이 에라토스테네스의 체(yuuj.tistory.com/156)를 이용해서 풀 수 있는 문제. import sys def primelist(n): arr = [True for _ in range(n+1)] for i in range(2, (int(len(arr)**0.5)+1)): if arr[i]: for k in range(i+i, len(arr), i): arr[k] = False return arr m, n = map(int, sys.stdin.readline().split(" "..