whdnjsdud551   3년 전

  1. 2부터 N까지 모든 정수를 적는다.
  2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
  3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
  4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

문제에 명시된 알고리즘에서 소수 2번에서 소수 p를 발견하고, 3번에서 p를 지우고, 아직 지우지 않은 p의 배수를 크기 순서대로 지우게 되어있습니다.

에라토스테네스의 체 알고리즘에 따르면 소수 p를 발견하면 p를 지우지 않고, p의 배수부터 지워가는 방식이 맞는것 같습니다.

3412mb   3년 전

이 문제에서 '지운다'라는 표현은 소수 집합에서 제거한다는 의미가 아닙니다.
예를 들어, 첫 번째 예제 7 3의 경우 2, 4, 6을 차례대로 지우기 때문에 6이 정답입니다.

djm03178   3년 전

문제를 유연하게 해석할 필요가 있습니다. 지운다고 해서 이미 P를 찾았다는 사실 자체가 없어지는 것은 아닙니다. 지우기 전에 머릿속으로 외우든, 다른 곳에 옮겨적든지 하면 됩니다. 에라토스테네스의 체로서의 기능에는 전혀 문제가 없습니다.

whdnjsdud551   3년 전

문제에서 요구하는 답을 도출하기 위해 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)라 나와있어 에라토스테네스의 체 알고리즘과 문제의 알고리즘이 차이가 있다는 점에서 의문이 있었습니다.

djm03178   3년 전

에라토스테네스의 체라는 것이 연산 단위로 구현체가 하나로 딱 정해진 것이 아닙니다. 위키피디아에서 제시한 것은 그 중 동작하는 하나의 방식을 제시한 것뿐이고 모든 에라토스테네스의 체 구현체가 해당 절차를 100% 똑같이 밟아야만 하는 것은 아닙니다. 해당 알고리즘에서 사용한 원리가 같으면 같은 알고리즘이라고 할 수 있습니다. '지우고 남은 것을 소수로 취급'하느냐, '지우는 것과 별개로 소수인 것들을 선별하는 과정을 중도에 두느냐'는 그야말로 구현체의 차이입니다.

댓글을 작성하려면 로그인해야 합니다.