[백준(baekjoon) 6588] 소수 구하기 문제 백준 6588 ‘4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.’ 하나 이상의 테스트 케이스 T가 주어질 때(0이 나오면 끝), 다음과 같은 규칙으로 출력하라 답이 존재 : T = a + b출력 (답이 여러개일 경우 b - a가 가장 큰 것) 답이 없음 : Goldbach's conjecture is wrong.출력 예시 8 = 3 + 5 20 = 3 + 17 42 = 5 + 37 해결 알고리즘 소수를 만드는 방식은 에라토스테네스의 체를 이용하였다. 자세한 방법은 에라토스테네스의 체로 소수 구하기 참고! 방법 T = a + b를 만족하는 홀수 소수 a, b는 많을 것이다. 따라서, 가장 큰 b - a를 찾기 위해 조건을 만족하는 가장 ..

[백준(baekjoon) 1929] 소수 구하기 문제 백준 1929 M 이상 N 이하인 소수를 모두 출력하시오. (1≤M≤N≤1,000,000) 해결 알고리즘 두가지 방식으로 풀었다. 1. 소수로 나누기 소수인지 확인하기 위해 자신보다 작은 소수들로 모두 나누어 확인하는 방법 n개의 수에 자신보다 작은 소수들의 개수k만큼 모두 확인하여야 한다. 곱해서 n이 되는 수 중 가장 큰 수인 이하로만 검사하면 된다. 2. 에라토스테네스의 체 소수의 배수들 지워나가는 방법 O(n log log n) 시간복잡도를 가진다. 자세한 내용 방법 소수 여부를 저장해 둘 [N + 1]크기의 배열을 생성한다. 가장 작은 소수 2부터 시작하여 수들을 차례대로 확인한다. 지워지지 않은 경우 해당 수는 소수이다. 소수의 배수들을 모..