시냅스

https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 6 이상의 짝수는 두 개의 소수의 합으로 이뤄진다는 골드바흐의 추측을 구현하는 문제였다. 입력받은 숫자와, 두 개의 소수를 한 번에 출력해주면 되는 문제였다. 소수의 경우 에라토스테네스의 체를 사용했는데, 에라토스테네스 체를 구현하는 두 방식을 비교하여 조금 더 빠른 방식을 확인하였다. EOFError를 통해 끝까지 입력 받을 수 있게 했고, input 값이 0이라면 프로그..

https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 역시 이 문제 또한 일반 반복문을 통하여 해결하였을 때에는 시간초과로 틀리게 된다... 유클리드 호제법이란 것을 활용해야 하는데, 유클리트 호제법이란 x, y의 최대공약수는 y, x % y 의 최대공약수와 같다는 원리를 이용한다. x % y 의 값이 0이 됐을 때의 y 값이 결국 최대 공약수가 된다. 이게 뭔소리냐면... 10 과 6 을 예시로 든다면, x y x%y 10 6 4 6 4 2 4 2 0 결국, 최대 공약수는 2 이다. 증명은 나무위키에 잘 나와 있다..

https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 너무 많은 시간 초과들과의 싸움이 있었고... 더는 시간초과로 골머리 썩고 싶지 않은 마음에 애초에 에라토스테네스의 체를 활용하여 문제를 풀었다. 문제에서 주어진 시간이 넉넉하여 이렇게 풀지는 않아도 될 것 같다. 문제는 최대 1000 까지의 숫자가 최대로, 미리 모든 수를 1로 채운 배열을 하나 생성하였다, 이후 모든 수의 배수는 0으로 바꿔, 소수가 아님을 표시했다. 이후 입력받은 수를 위 만들어 둔 배열에서 확인하는 식으로 풀이하였다. code max_val ..