에라토스테네스의 체

백준 / 수학 / 2960번 / 에라토스테네스의 체 / JS

문제 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. 이 알고리즘은 다음과 같다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(1, K) < N ≤ 1000) 출력 첫째 줄에 K번째 지워진 수를 출력한다. 예제 입력 1 7 3 예제 출력 1 6 /* 에라토스테네스의 체 */ const fs = require('fs'); cons..

에라토스테네스의 체

에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수 구하기 알고리즘이다. 알고리즘 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. (위는 120까지가 예시) 짝수 중 유일하게 2는 소수이므로 2는 소수로 체크해준다. (빨간색) 2를 제외한 2의 배수를 모두 지워준다. 3은 소수이므로 3은 소수로 체크해준다.(초록색) 3을 제외한 3의 배수를 모두 지워준다. 5는 소수이므로 5는 소수로 체크해준다.(파란색) 5를 제외한 5의 배수를 모두 지워준다. ... 3~4단계의 과정을 소수를 만날때마다 해주면된다. 간단하게 말해서, 본인이 설정한 범위의 최댓값을 x라고 한다면, 2부터 시작해서 x까지 소수의 배수를 다 지워버리면 된다. 코드(C++)로는 아래와 같이 나타낼 수 있다. voi..