1929 - 소수 구하기

(문제보기)

www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

소수 구하기 성공분류

2 초

256 MB

83948

23456

16667

27.321%

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력 1 복사

3 16

예제 출력 1 복사

3 5 7 11 13

1. 문제분석

 

무려 정답 비율이 27.321%, 매우 낮은 정답률을 보여주고 있는 문제이다.

 

문제의 요구사항은 매우 간단하다.

 

• 시작숫자 M과 끝 숫자 N을 준다.
• M과 N 사이의 소수를 모두 출력하라.

다만, 시간제한이 빡빡해서 앞에서 해결한 소수의 풀이방법으로는 안풀린다.

 

모두 시간초과에 걸리기 때문이다..

 

그래서 소수를 찾는 다른 방법이 있나 찾아봤다.

 

2. 에라토스테네스의 체

 

소수를 구하는 방법중 아주 유명한 방법인 에라토스테네스의 체라는 방법이 있었다.

사실 나도 잘 몰랐는데,,, 이 방법에서의 핵심 사항은 다음과 같다.

 

• N에 대하여, N은 제곱근 N보다 크지않은 어떤 소수로도 나누어지지 않는다.
• 즉, (어떤수)/(어떤수) = 몫 + 나머지에서, 몫과 나머지 둘둥 하나는 무조건 N의 제곱근보다 작다.
• 쉽게 말하면 제곱근N보다 큰 소수로는 나눠지지 않으므로 소수임을 판별할 때 제곱근N 이하의 수만 비교하면 된다.

여기서 에라토스테네스의 채라는 방법이 있다.

어떤 구간이 있을 때, 작은 값부터 소수를 찾아가는데, 소수를 찾았다면 그의 배수들은 모두 제외한다.

 

예시로, 3~10의 구간이 있다고 생각해보자.

 

 [ 3 4 5 6 7 8 9 10 ] 

 

먼저, 소수 2를 찾았다. 그러므로 2의 배수들은 구간에서 모두 제외된다.

 

[ 3 4 5 6 7 8 9 10 ]

 

다음, 소수 3을 찾았다. 3의 배수들을 모두 제외한다.

 

[ 3 4 5 6 7 8 9 10 ]

 

다음은 소수 5, 다음은 소수 7을 찾는다. 나머지는 소수가 아니므로 소수 찾기가 끝난다.

 

[ 3 4 5 6 7 8 9 10 ]

 

소수 : 3, 5, 7

 

이 방법에서 위의 핵심사항을 적용시킨다.

즉, 소수를 계속해서 찾아 나가나, 제곱근N까지만 찾는 것이다.

 

에라토스테네스의 체와 관련된 내용은 구글에 검색하면 더 좋은 자료들이 많다. 참고하길 바란다.

 

 

3. 소스코드

 

이전에 해결했던 소스코드가 재채점 되면서 틀렸습니다.

따라서 소스코드를 수정했습니다.

 

#include<iostream>
#include<math.h>

using namespace std;

int main(void) {
	int arr[1001] = { 0 };
	int m, n;
	cin >> m >> n;

	int max;

	int cnt = 0;
	for (int i = m; i <= n; i++) {
		max = sqrt(i);
		cnt = 0;
		for (int j = 2; j <= max; j++) {
			if (i % j == 0) cnt++;
			if (cnt != 0) {
				arr[i] = -1;
				break;
			}
		}
		if (cnt == 0) arr[i] = 1;
	}

	arr[1] = -1;
	for (int i = m; i <= n; i++)
		if (arr[i] != -1) cout << i << "\n";
}

 

이전 소스코드.

// #1929
#include<stdio.h>
#include<math.h>

int main(void){
        int M, N;
        int length;
        scanf("%d %d", &M, &N);

        length = N-M+1;

        int array[length];
        //set array
        for(int i=0; i<length; i++){
                array[i] = M;
                M++;
        }


        //select data
        for(int i=2; i<sqrt(N); i++)
                for(int j=0; j<length; j++)
                        if(array[j] != -1 && array[j]%i == 0 && array[j] != i)
                                array[j] = -1;

        //1 is not prime number
        if(array[0] == 1) array[0] = -1;

        //print prime number
        for(int i=0; i<length; i++)
                if(array[i] != -1) printf("%d\n", array[i]);

        return 0;
}

 

소스자체가 깔끔하진 않지만,,, 돌아간다는 것이 감격스러웠다.

 

비록 중간중간에 딴짓을 하긴 했는데 한문제로 무려 2시간이나 잡아먹었다.

정답률이 왜 낮은지 알것 같았다.

 

소스코드를 최적화하고 싶은데... 이렇게 많이 시도를 하니까 지친다...

그러니까 소스가 좀 더러워도 이해해주면 감사하겠다..