이 문제에서 '지운다'라는 표현은 소수 집합에서 제거한다는 의미가 아닙니다.
예를 들어, 첫 번째 예제 7 3의 경우 2, 4, 6을 차례대로 지우기 때문에 6이 정답입니다.
2960번 - 에라토스테네스의 체
문제에서 요구하는 답을 도출하기 위해 p를 지우는것은 이해 했습니다.
하지만 원래 에라토스테네스의 체 알고리즘에서는 소수와 소수가 아닌 수를 구분하는것이 목적에 있기 때문에 문제에서 제시하는 알고리즘과 에라토스테네스의 체 알고리즘이 같은 기능을 하는지에 대한 의문이 있습니다.
위키피디아에서 "Enumerate the multiples of p by counting in increments of p from 2p to n, and mark them in the list (these will be 2p, 3p, 4p, ...; the p itself should not be marked)" 이와 같은 문장으로 되어있는데, 해석에 따르면 p의 배수부터 지우는것(mark)으로 되어있고 p자신은 지우지 않는다(p itself should not be marked)라 나와있어 에라토스테네스의 체 알고리즘과 문제의 알고리즘이 차이가 있다는 점에서 의문이 있었습니다.
댓글을 작성하려면 로그인해야 합니다.
whdnjsdud551 3년 전
문제에 명시된 알고리즘에서 소수 2번에서 소수 p를 발견하고, 3번에서 p를 지우고, 아직 지우지 않은 p의 배수를 크기 순서대로 지우게 되어있습니다.
에라토스테네스의 체 알고리즘에 따르면 소수 p를 발견하면 p를 지우지 않고, p의 배수부터 지워가는 방식이 맞는것 같습니다.