전공/알고리즘 + 코테
[C 언어] 백준 #1929 - 소수 구하기
BBungyaLog
2023. 7. 14. 22:50
문제
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
출력
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
| 입력 | 출력 |
| 3 16 | 3 5 7 11 13 |
풀이
처음에 푼 방식
n부터 m까지 x에 대해 1부터 x까지 소수를 판별하는 방법으로 코드를 짰다. 그러나 이 코드는 시간 초과로 실패하였다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int isPrime(int a)
{
int cnt = 0;
for (int i = 1; i <= a; i++)
if (a % i == 0)
cnt++;
if (cnt == 2)
return 1;
else
return 0;
}
int main(void)
{
int n, m;
scanf("%d %d", &n, &m);
for (int i = n; i <= m; i++) {
if (isPrime(i) == 1)
printf("%d\n", i);
else
continue;
}
return 0;
}
무엇이 잘못되었을까 검색을 해봤는데 이 문제는 에라토스테네스의 체 알고리즘을 이용해야한다는 것을 알아냈다.
두번째로 푼 방식
소수: 1과 자기 자신으로만 나눠지는 숫자
에라토스테네스의 체: 소수를 빠르게 찾는 방법이다.
에라토스테네스의 체를 이용하여 소수를 찾는 순서 >>
- 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
- 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
- 자기 자신을 제외한 2의 배수를 모두 지운다.
- 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
- 자기 자신을 제외한 3의 배수를 모두 지운다.
- 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
- 자기 자신을 제외한 5의 배수를 모두 지운다.
- 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
- 자기 자신을 제외한 7의 배수를 모두 지운다.
- 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. (보라색)
이 방식을 사용하면 1부터 자기 자신까지 소수를 판별하지 않아 시간을 단축할 수 있다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, m;
int primeNum[1000001] = {0, 1};
scanf("%d %d", &n, &m);
for (int i = 2; i <= m; i++)
for (int j = 2; j * i <= m; j++)
primeNum[j * i] = 1;
for (int i = n; i <= m; i++)
if (primeNum[i] == 0)
printf("%d\n", i);
return 0;
}