백준 알고리즘 기초/수학
[백준][수학]골드바흐의 파티션
코딩고치
2019. 9. 13. 23:30
17103번: 골드바흐 파티션
첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.
www.acmicpc.net
짝수 N을 두 소수의 합으로 나타낼 때 N에 대한 두 소수의 합의 개수를 출력하는 문제. 기존에 풀었던 골드바흐의 추측에서 작성한 코드를 이용하면 쉽게 풀 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include <iostream>
using namespace std;
const int Max = 1000000;
bool arr[Max + 1];
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
arr[0] = arr[1] = true;
for (int i = 2; i * i < Max; i++)
{
if (arr[i] == false)
{
for (int j = i + i; j <= Max; j += i)
arr[j] = true;
}
}
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
int count = 0;
for (int i = 2; i <= n/2; i++) // 순서만 다른 것을 count하지 않기 위해 i<=n/2
{
if (arr[i] == false && arr[n - i] == false)
count++;
}
cout << count << '\n';
}
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
골드바흐의 추측
4보다 큰 짝수를 두 소수 홀수의 합으로 출력하는 코드를 작성하는 문제이다. 백만 이하의 수 중에서 소수를 찾기 위해 에라토스테네스의 체를 이용하였다. 에라토스테네스의 체는 소수를 구하는 방법으로 다음과..
codingcocoon.tistory.com