에라토스테네스의 체

문제 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 코드 My answer import sys import math input = sys.stdin.readline n, m = map(int, input().split()) array = [1 for i in range(m+1)] for i in range(2, int(math.sqrt(m))+1): if (array[i] == 1): j = 2 while (i*j =M): print(i) 풀이 이 문제는 전형적인 소수 구할 때 쓰는 방법인 에라토스테네스의 체를 이용하여 푸는 방법이다. 대..

오늘은 은근 자주 나오는 유클리드 호제법과 에라토스테네스의 체에 대해서 설명해보겠다. 우선 유클리드 호제법은 최대공약수를 구하는 알고리즘이다. 최대공약수를 알면 최소공배수도 쉽게 알 수 있기 때문에 유클리드 호제법은 보통 최대공약수와 최소공배수를 구할 때 모두 쓰인다. 우선 바로 코드부터 보여주자면 if(b>a) : a,b = b,a while(b!=0): a=a%b a,b=b,a print(a) 우선 입력받은 두 수중에 큰 수를 정해놓고 큰 수를 작은 수로 계속 나누어서, 나누어 떨어질 때까지 반복한다. 나누어 떨어질 때(나머지가 0일 때), 나누는 수가 최대공약수이다. 이 방법은 a,b의 최대공약수는 (a-b),a의 최대공약수와 같다는 성질 때문이다. 이 때 최소공배수는 a*b를 a와 b의 최대공약수..