저는 이 문제를 풀지 않아 조심스럽습니다만, sieve에서 primes[4] = 1로 유지됩니다. 그 외에도 74, 82, 86 등의 짝수에서 primes 벡터의 값이 1인 것을 확인했습니다. 보통의 구현처럼 탐색을 2부터 시작하지 않아서 그런 것으로 보입니다.
17105번 - 골드바흐 트리플
저는 이 문제를 풀지 않아 조심스럽습니다만, sieve에서 primes[4] = 1로 유지됩니다. 그 외에도 74, 82, 86 등의 짝수에서 primes 벡터의 값이 1인 것을 확인했습니다. 보통의 구현처럼 탐색을 2부터 시작하지 않아서 그런 것으로 보입니다.
하 이거때메 4가 소수로 판정됐었네요ㅋㅎㅋㅎㅋㅎ
진짜 답변자님 없었으면 절대 못 찾았을 것 같습니다 감사합니다
댓글을 작성하려면 로그인해야 합니다.
luckyandykang 1년 전
예제나 직접 대입해본 테스트 케이스 모두 성립합니다. 예제가 충분히 일반적이라고 판단해 제출했는데, 5%에서 틀립니다.
이유를 모르겠습니다. 도와주시면 감사하겠습니다.
a : 100000까지 소수
b : 3 이상의 소수를 절반으로 압축
c, d : b를 제곱, 세제곱
e : b의 모든 지수를 2배
f : 르모앙의 추측(p + 2q)인데 q가 홀수 소수인 것만 카운트
이때 d에서 p + q + r은 6번, p + 2q는 3번, 3p는 1번 카운팅된 것에 집중해 p + 2q를 3번, 3p를 2번 더 카운팅해 모든 순열을 6회씩 카운팅한 뒤
마지막에는 답을 6으로 나누고, N - 4가 소수인 경우 1을 더하는 로직으로 진행했습니다.
수정) 코드는 스포 방지용으로 삭제했습니다. 여러분은 저같이 바보처럼 에라토스테네스를 3부터 시작해서 4를 소수로 판정하는 대참사가 일어나지 않기를 바랍니다…ㅠㅜ
추가 수정) 에라토스테네스 탐색을 3부터 시작한 이유가 홀수 소수만 다루기였는데 이렇게 푸실 분들은 마지막에 2만 따로 처리하시면 됩니다