본문 바로가기

백준 알고리즘 단계별 풀이 (문제 수)/기본 수학 2 (6)6

[C++] 골드바흐의 추측 : 9020번 문제 골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다. 2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다. 14 = 3 + 11, 14 = 7 .. 2022. 7. 6.
[C++] 베르트랑 공준 : 4948번 문제 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 시간제한 : 1초 입력범위 : 1 ≤ n ≤ 123,456 해석 문제를 풀기 위해서는 '에라토스테네스의 체' 를 알아야만 한다. 이걸 몰라도 구현과 결과는 나오겠지만, 백준 사이트에서 시간초과가 날 것이다. 에라토스테네스의 체는 생각보다 별거없다. 구하고자 하는 범위까지의 소수를 구하는 알고리즘이다. 방법은 다음과 같다. 1. 구하고자 하는 범위의 모든 숫자를 나열한다. 2. 2의 두번째 배수(4) 부터 시작하여 2의 배수를 모두 제거한다. 3. 3의 두번째 배수(6) 부터 시작하여 3의 배수를 모두 제거한다. 4. 이 과정을 반복하여 어떤 소수의 모든 배수를 제거한다. 5. 범위 내에는 소수.. 2022. 7. 6.
[C++] 소수 구하기 : 1929번 문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 예제 입력 3 16 예제 출력 3 5 7 11 13 해석 소수를 판별하는 방법은 아래 링크를 참고한다. [C#] 소수 찾기 : 1978번 (tistory.com) [C#] 소수 찾기 : 1978번 이번 문제는 C# 으로 구현하였습니다! 문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 해석 소수가 되기 위해선 1과 자기자신으로만 나누어져야 한다. 바 wildgoosechase.tistory.com 풀이 #include #include using namespace std; int main() { int M, N; // 범위 bool isPrime = true; cin >> M >> N; for (int i.. 2022. 7. 6.
[C++] 소인수분해 : 11653번 문제 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오. N이 1인 경우 아무것도 출력하지 않는다. 예제 입력 72 예제 출력 2 2 2 3 3 해석 어떤 수 N을 소인수 분해한다는 것은 소수들의 곱으로만 이루어지도록 만드는 것을 의미한다. 따라서 가장 작은 소수 2부터 나누어 떨어진다면 소인수분해를 1차례 진행한 것이다. 반복적으로 2 와 N - 1 사이까지 나누면서 나누어 떨어지는 시점이 발생하면, 나누어서 얻은 새로운 몫인 N 과 새로운 연산을 하며 N이 더이상 나누어지지 않을 때 까지 진행하면 된다. 마지막으로는, 최종으로 남은 N 까지 출력하면 소인수분해가 완료된다. 풀이 #include #include using namespace std; int main() { int N; // 주.. 2022. 7. 6.
[C++] 소수 (제곱근을 활용하여 소수 판별) : 2581번 문제 자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다. 문제 해석 이전 문제와 동일한 방법으로 소수를 판별하면 된다. 단 범위를 입력받으므로, 반복문의 범위를 입력받은 값으로 설정해주는 것과 소수들을 모두 더한 합, 그리고 최솟값을 추가로 출력해주면 된다. + 소수를 판별함에 있어서 2 ~ 자기자신 사이의 모든 수로 나누어보아도 되지만, 2 ~ 자기자신의 제곱근까지만 나누어보면 더 빠르게 판별할 수 있다. 12의 경.. 2022. 7. 5.
[C#] 소수 찾기 : 1978번 이번 문제는 C# 으로 구현하였습니다! 문제 주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오. 해석 소수가 되기 위해선 1과 자기자신으로만 나누어져야 한다. 바꿔말해, 2와 자기 자신 - 1 사이의 숫자로 나누었을 때, 나머지가 0 이 아니면 소수가 아니다. 따라서, 입력받은 수를 2부터 입력받은 수 까지 나누어 나머지가 생기면 소수가 아니라고 판별하고, 그 외의 경우만 소수로 갯수를 세면 된다. 하지만, 2부터 자기자신 - 1 까지 일일히 확인하는 것보다 계산 속도를 줄일 수 있는 방법이 존재한다.이는 다음 링크를 참고하면 알 수 있다. [C++] 소수 (제곱근을 활용하여 소수 판별) : 2581번 (tistory.com) [C++] 소수 (제곱근을 활용하여 소수 판별) .. 2022. 7. 5.

티스토리툴바