개발아 담하자

문제 1929 번 : 소수 구하기 문제 링크 : https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) www.acmicpc.net 문제 M 이상 N 이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 단순한 소수 찾기로 구하면 메모리 초과가 발생한다. 에라토스테네스의 체 알고리즘을 사용해야 한다. 에라토스테네스의 체 란? 👇 https://silver-g-0114.tistory.com/39?categ..

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체 '라고 부른다. 구현 과정 120까지의 모든 소수를 구한다고 해 보자. 에리스토테네스의 체는 2부터 120까지의 수를 배열에 모두 넣은 후 소수가 아닌 것들으 모두 체크해버리는 것이다. 즉, 체크가 안 된 수들이 소수 이다. 2. 2를 제외한 2의 배수 지우기 2. 3을 제외한 3의 배수 지우기 3. 4의 배수는 지울 필요 없다 (2의 배수에서 이미 지워짐) 2,3 다음으로 남아있는 가장 작은 수인 5를 제외한 5의 배수를 지운다. 이런 식으로 남은 것들의 2배수, 3배수, ... n배수를 지우다 보면 소수만 남는다. 이미 정해진 소수의 배수인 것들은 지워서 소수를 ..