ALiNew ALiNew

골드바흐의 추측

• [Algo Rhythm🕺💃]BOJ 6588 - 골드바흐의 추측

  Algo Rhythm🕺💃/BOJ 2021. 6. 23. 17:45

  문제 분석 이 문제는 4보다 큰 어떤 짝수 $x (6 \le x \le 10^6)$가 두 홀수인 소수 $a, b (a \le b)$의 합으로 나타낼 수 있는지 판별하는 문제이다. 이때 주의할 점은 골드바흐의 추측은 $10^{18}$ 이하에서 참임이 확인되었기 때문에 두 홀수 소수의 합으로 나타내지 못 하는 경우는 생각하지 않아도 된다는 것이다. 문제 풀이 1. '소수 판별 알고리즘' 응용 주어진 $x$에 대하여 $a$의 가능한 최소값인 3부터 $x - a$인 $b$가 2보다 크지 않을 때까지 $a, b$ 모두 소수인지 판별한다. 만약 모두 소수라면 $x = a + b$를 출력한 뒤 반복문을 탈출하고 그렇지 않다면 $a$를 2씩 증가하고 위 과정을 반복한다. 이때 2씩 증가하는 이유는 짝수는 절대 소수가 ..

  Read More