[C++] 백준/Silver/6588. 골드바흐의 추측

2025. 2. 18. 21:08·C++/Algorithm

문제: 골드바흐의 추측 (백준 6588번)

문제 분석

골드바흐의 추측은 "4 이상인 모든 짝수는 두 개의 소수의 합으로 나타낼 수 있다" 는 정수론의 가설이다.
이 문제에서는 n이 주어졌을 때, 두 소수의 합으로 표현하는 방법을 찾아 출력하는 것이 목표이다.


  1. 에라토스테네스의 체를 이용한 소수 판별
    • 100만까지의 숫자에서 소수를 빠르게 판별하기 위해 에라토스테네스의 체를 사용한다.
    • prime[i]가 true이면 소수, false이면 합성수로 설정한다.
  2. 두 포인터를 활용한 탐색
    • left는 2부터 시작하고, right는 n부터 시작한다.
    • 두 포인터가 가리키는 값이 소수인지 확인하면서,
      • 합이 n보다 크다면 right를 줄인다.
      • 합이 n보다 작다면 left를 증가시킨다.
    • 합이 n이 되는 순간 두 수를 출력한다.

전체 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	vector<bool> prime(1000000, true);
	for (int i = 2; i < 1000; i++) {
		if (!prime[i])continue;
		for (int j = i + i; j < 1000000; j += i) {
			prime[j] = false;
		}
	}
	while (n) {
		int left = 2, right = n;
		cout << n << " = ";
		while ((left + right) != n) {
			if (left + right > n)
			{
				do { right--; } while (!prime[right]);
			}
			else if (left + right < n)
			{
				do { left++; } while (!prime[left]);
			}
		}
		cout << left << " + " << right << '\n';
		cin >> n;
	}
}

 

'C++ > Algorithm' 카테고리의 다른 글

[C++] 백준/Silver/1325. 효율적인 해킹  (0) 2025.02.20
[C++] 백준/Gold/12852. 1로 만들기 2  (0) 2025.02.19
[C++] 백준/Gold/9205. 맥주 마시면서 걸어가기  (1) 2025.02.17
[C++] 백준/Gold/10942. 팰린드롬?  (0) 2025.02.14
[C++] 백준/Gold/2589. 보물섬  (0) 2025.02.13
'C++/Algorithm' 카테고리의 다른 글
  • [C++] 백준/Silver/1325. 효율적인 해킹
  • [C++] 백준/Gold/12852. 1로 만들기 2
  • [C++] 백준/Gold/9205. 맥주 마시면서 걸어가기
  • [C++] 백준/Gold/10942. 팰린드롬?
돼지표
돼지표
https://github.com/wkdgns135
  • 돼지표
    돼지표 개발 스토리
    돼지표
  • 전체
    오늘
    어제
    • 분류 전체보기 (99)
      • C++ (58)
        • Algorithm (52)
      • Python (1)
      • Machine Learning (2)
      • Computer Graphics (4)
        • Curly Hair Simulation (2)
      • GPU Programming (11)
        • CUDA basic (7)
        • CUDA fluidsGL (4)
      • Unreal 5 (20)
        • Troubleshooting (4)
        • FPS Shooting (5)
        • Study (9)
        • EOS (1)
      • Computer Science (3)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

    • Github
  • 공지사항

  • 인기 글

  • 태그

    아이작 맵 생성
    Fluid Simulation
    unreal 5
    FPS
    그래프 탐색
    C++
    Algorithm
    Rendering Pipeline
    그리디 알고리즘
    위상 정렬
    구현
    BFS
    CUDA
    GPU Programming
    OpenGL
    UE5
    수학
    dp
    자료 구조
    CS
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
돼지표
[C++] 백준/Silver/6588. 골드바흐의 추측
상단으로

티스토리툴바