[Python] 백준(BOJ) 6588번: 골드바흐의 추측

문제 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 풀이 에라테스토스트의 체를 활용해서 최대값인 1000000까지의 소수 여부 모두 구하고, 그 후에 무한루프를 통해서 0이 들어오기 전의 값들에 대해 판별을 해주면 된다. 판별하는 방법은 가장 작은 소수(a)부터 하나씩 n-a도 소수인지 확인을 하면 되는데, list에서 in을 사용할 경우 시간복잡도가 O(n) 이 되기 때문에 따로 소수 리스트를 만들지 않고, arr을 그대로 사용해서 소수인지 아닌지 확인하는 시간을 O(1)으로 줄였다..
PS/Python 2020. 12. 9. 03:56
1