알고리즘 문제/[백준]
[백준] 9020 골드바흐의 추측
latter2005
2021. 3. 4. 18:09
9020번: 골드바흐의 추측
1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아
www.acmicpc.net
문제 확인
소수 관련 문제입니다. 범위가 10000으로 적으므로 에라토스테네스의 체 알고리즘으로 간단하게 풀 수 있습니다.
풀이
10000 이하의 수를 에라토스테네스의 채 알고리즘을 통해 소수를 미리 구해둡니다.
그 후 가장 가까운 두 소수를 찾기 위해 입력받은 수에서 2를 나눈 2개의 변수를 두고 하나는 증가, 하나는 감소하며 두 변수 모두 소수일 때 출력합니다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include <cstdio>
#include <string.h>
int main(){
int n;
char p[10001];
memset(p, 1, 10001);
p[1] = 0;
for (int i = 2; i*i <= 10000; i++)
if (p[i])
for (int j = i * i; j <= 10000; j += i)
p[j] = 0;
scanf("%d", &n);
for (; ~scanf("%d", &n);) {
int x = n / 2, y = x;
while (!p[x] || !p[y]) { x--; y++; }
printf("%d %d\n", x, y);
}
}
|
cs |
반응형