https://www.acmicpc.net/problem/17103
17103번: 골드바흐 파티션
첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.
www.acmicpc.net
방법1
|
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
38
39
40
41
42
43
44
45
46
47
48
49
|
import java.io.*;
public class Main {
public static void main(String[] args) {
try {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int iMax = 1000000;
boolean[] arrNotPrimeCheck = new boolean[iMax + 1];
int[] arrPrime = new int[80000];
int primeCount = 0;
for (int i = 2; i * i <= iMax; i++) {
for (int j = i; j * i <= iMax; j++) {
arrNotPrimeCheck[i * j] = true;
}
}
for (int i = 2; i <= iMax; i++) {
if (arrNotPrimeCheck[i] == false) {
arrPrime[primeCount++] = i;
}
}
int iTotalCase = Integer.parseInt(br.readLine());
while (iTotalCase-- > 0) {
int num = Integer.parseInt(br.readLine());
int count = 0;
for (int i = 0; i < primeCount && arrPrime[i] <= num / 2; i++) {
if (num - arrPrime[i] >= 2) {
if (arrNotPrimeCheck[num - arrPrime[i]] == false) {
count += 1;
}
}
}
sb.append(count).append("\n");
}
System.out.println(sb.toString());
} catch (Exception e) {
e.printStackTrace();
}
}
}
Colored by Color Scripter
|
c++소스
더보기
|
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include <iostream>
using namespace std;
const int MAX = 1000000;
bool isno_prime[MAX + 1];
void do_prime_sieve()
{
for (int i = 2; i * i <= MAX; i++)
{
if (!isno_prime[i])
{
for (int j = 2; j * i <= MAX; j++)
{
isno_prime[j * i] = true;
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// 에라토스테네스의 체
do_prime_sieve();
int T;
cin >> T;
while (T--)
{
int N;
cin >> N;
int ptt_cnt = 0;
for (int i = 2; i <= N / 2; i++)
{
// i와 N-i가 모두 소수이면
if (!isno_prime[i] && !isno_prime[N - i])
{
ptt_cnt++;
}
}
cout << ptt_cnt << '\n';
}
return 0;
}
Colored by Color Scripter
|
방법2
|
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
38
39
40
41
42
43
44
45
46
47
|
import java.io.*;
public class Main {
public static void main(String[] args) {
try {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int iMax = 1000000;
boolean[] arrNotPrimeCheck = new boolean[iMax +1];
int[] arrIsPrime = new int[80000];
int primeCount = 0;
for (int i = 2; i<= iMax; i++ ) {
if (arrNotPrimeCheck[i] == false) {
arrIsPrime[primeCount++] = i;
for (int j = i * 2; j <= iMax; j += i) {
arrNotPrimeCheck[j] = true;
}
}
}
int iTotalCase = Integer.parseInt(br.readLine());
while (iTotalCase-- > 0) {
int num = Integer.parseInt(br.readLine());
int count = 0;
for (int i = 0; i < primeCount && arrIsPrime[i] <= num/2; i++) {
if (num - arrIsPrime[i] >= 2) {
if (arrNotPrimeCheck[num - arrIsPrime[i]] == false) {
count += 1;
}
}
}
sb.append(count).append("\n");
}
System.out.println(sb.toString());
} catch (Exception e) {
e.printStackTrace();
}
}
}
Colored by Color Scripter
|
c++소스
더보기
|
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
#include <iostream>
#include <vector>
using namespace std;
const int MAX = 1000000;
bool isno_prime[MAX + 1];
vector<int> primes;
void do_prime_sieve()
{
// 소수 벡터를 만들어야 하므로,
// 포문을 MAX범위까지 돌려야 한다.
for (int i = 2; i <= MAX; i++)
{
if (!isno_prime[i])
{
primes.push_back(i);
for (int j = 2; j * i <= MAX; j++)
{
isno_prime[j * i] = true;
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// 에라토스테네스의 체
do_prime_sieve();
int T;
cin >> T;
while (T--)
{
int N;
cin >> N;
int ptt_cnt = 0;
for (int i = 0; i < primes.size(); i++)
{
// N = 소수1 + 소수2 (소수1 <= 소수2) 이므로
// 소수1 <= N / 2
if (primes[i] > N / 2)
{
break;
}
if (N - primes[i] >= 2 && isno_prime[N - primes[i]] == false)
{
ptt_cnt++;
}
}
cout << ptt_cnt << '\n';
}
return 0;
}
Colored by Color Scripter
|
방법 2가 더 빠르다.
골드바흐의 추측문제는 조건을 만족하는 쌍 1개라도 찾으면 true로 체킹하고 넘어가는 문제였는데,
골드바흐 파티션 문제는 조건을 만족하는 쌍의 개수를 모두 찾는 것이다.
TIP1
소수 구하기 - 에라토스테네스의 체에서 고생을 많이 했다 ㅠㅠ
방법 1 도 되고
|
1
2
3
4
5
6
7
8
9
10
11
|
for (int i = 2; i * i <= 1000000; i++) {
for (int j = i; j * i <= iMax; j++) {
arrNotPrimeCheck[i * j] = true;
}
}
for (int i = 2; i <= 1000000; i++) {
if (arrNotPrimeCheck[i] == false) {
arrPrime[primeCount++] = i;
}
}
Colored by Color Scripter
|
방법2 도 되는데
|
1
2
3
4
5
6
7
8
9
10
|
for (int i = 2; i<= 1000000; i++ ) {
if (arrNotPrimeCheck[i] == false) {
arrPrime[primeCount++] = i;
for (int j = i * 2; j <= 1000000; j += i) {
arrNotPrimeCheck[j] = true;
}
}
}
Colored by Color Scripter
|
방법3 는 왜 안될까???
|
1
2
3
4
5
6
7
8
|
for (int i = 2; i * i <= 1000000; i++) {
if (arrNotPrimeCheck[i] == false) {
arrPrime[primeCount++] = i;
for (int j = i; j * i <= 1000000; j++) {
arrNotPrimeCheck[i * j] = true;
}
}
}
Colored by Color Scripter
|
결론부터 말하자면, 방법 3은 소수인것을 arrPrime배열에 덜 넣는다.
방법 3은 i가 1000일 때까지 밖에 반복문을 돌지 않으므로,
1000 이후의 소수를 배열에 추가하지 않는 것이다.
참고: 에라토스테네스의 체 자체는 방법 1, 2, 3 모두 옳다.
TIP2
|
1
|
for (int i = 0; i < primeCount && arrIsPrime[i] <= num/2; i++)
|
조사대상 수를 num, 그 이하의 수를 i 라 하면,
num/2 이하의 소수 i 에 대해서만 조사하자
그러면 쓸데없이 0~num 까지 모두 반복문을 돌리지 않아도 된다.
'Algorithm > BOJ' 카테고리의 다른 글
| [BOJ]2745번: 진법 변환(java, c++) (0) | 2019.09.25 |
|---|---|
| [BOJ]11005번: 진법 변환 2(java, c++) (0) | 2019.09.25 |
| [BOJ]2089번: -2진수(java, c++) (0) | 2019.09.23 |
| [BOJ]1212번: 8진수 2진수(java, c++) (0) | 2019.09.23 |
| [BOJ]1373번: 2진수 8진수(java, c++) (0) | 2019.09.23 |
댓글