모두의 dream
백준 1929 본문
Contents
접기
1929번: 소수 구하기
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
www.acmicpc.net
#include<stdio.h>
int main()
{
int N=0, M=0;
int flag=0;
scanf("%d %d", &M, &N);
for(int i=M; i<=N; i++)
{
if(i == 1)
continue;
flag = 0;
for(int j=2; j<i; j++)
{
if(i % j == 0)
{
flag = 1;
break;
}
}
if(flag == 0)
printf("%d\n", i);
}
return 0;
}
// 소수를 구하는 방법 중 가장 비효율적인 방법이라고 한다.
처음에 짠 코드. 직접 다 나눠서 나머지를 가지고 비교하는 방식으로 최대한 반복횟수를 줄인다고 break도 써보고 했지만 그럼에도 불구하고 시간초과로 실패했다.
구글링을 해보니까 직접 나눠서 하는 방식은 가장 비효율적이고, 소수를 구하는 방법중 "에라토스테네스의 체" 가 효율적이라는 것을 알게 되었다.
(시간복잡도에 대한 개념을 다시 공부해보면 좋을 것 같다. 가장 효율적인 소스코드를 짜는 방법과 함께...)
에라토스테네스의 체는 앞에서부터 2가 소수면 2의 배수는 모두 지우고, 3이 소수면 3의 배수는 모두 지우면서 쭉 끝까지 정리하는 방식이다.
참고: 백준 1929번 C언어 소수구하기 - 성공 (velog.io)
#include<stdio.h>
int main()
{
int arr[100] = {0, };
int N=0, M=0, cnt=0;
arr[1] = 1;
scanf("%d %d", &M, &N);
for(int i=2; i<=N; i++)
{
if(arr[i] == 1) // 이미 소수가 아니라면 과정 패스
continue;
cnt = 2;
while(i*cnt <= N) // N의 값보다 커질때 까지 반복해서 에라토스테네스의 체 구현
{
arr[i * cnt] = 1; // 소수가 아니라면 1로 바꿔줌
cnt++;
}
}
for(int i=M; i<=N; i++)
{
if(arr[i] == 0)
printf("%d\n", i); // 최종적으로 0인 값, 즉 소수만 출력
}
return 0;
}
// 에라토스테네스의 체 (어짜피 범위만 보여주면 되니까 미리 배열을 만들어 놓고 출력만 함)
그래서 에라토스테네스의 체를 이용해서 짠 C코드.
에라토스테네스의 체를 이용하면 특정 범위 내의 소수를 출력시키기에는 좋으나, 어떤 수가 소수인가를 물어보는 프로그램에는 효율적이지 않을 것 같다.
Comments