소수
골드바흐의 추측 _ 백준 6588
이번에는 소수와 관련되어서, 조금 더 심화된 내용인 골드바흐의 추측과 관련된 문제입니다. 골드바흐의 추측은 문제에 나온대로, "4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다." 를 중심으로 이루어지는데요, 앞서서 풀었던 문제인 소수 찾기, 구하기의 알고리즘이 다시 활용됩니다. - 해당 코드는 아래 링크에. 2020/05/16 - [백준 문제풀이] - 소수 찾기 / 소수 구하기 _ 백준 1978,1929 소수 찾기 / 소수 구하기 _ 백준 1978,1929 1978번, 1929번 문제는 소수와 관련된 문제이다. 어떤 수 N이 소수가 아니라면, N = a * b 라고 표현할 수 있는데, 이떄 a와 b의 차이가 가장 적은 경우는 √n 이다. 그러므로, 검사를 n까지만 해서, 소수 runa-na..
소수 찾기 / 소수 구하기 _ 백준 1978,1929
1978번, 1929번 문제는 소수와 관련된 문제이다. 어떤 수 N이 소수가 아니라면, N = a * b 라고 표현할 수 있는데, 이떄 a와 b의 차이가 가장 적은 경우는 √n 이다. 그러므로, 검사를 n까지만 해서, 소수를 찾을 수 있다. 이러한 소수의 특징을 이용하면, 아래와 같은 함수를 만들 수 있다. (true = 소수 false = 소수아님) bool prime(int n) { if (n < 2) return false; for (int i = 2; i * i