[C++] 백준 1929번 / 소수 구하기

1929번: 소수 구하기

문제

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

 

 

입력

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

 

 

출력

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

 

 

예제 입력 1

3 16

예제 출력 1

3
5
7
11
13

 

 

해결 아이디어

(1 ≤ M ≤ N ≤ 1,000,000)범위로, 범위가 매우 커 O(n)복잡도로 접근하면 반복문이 두번 돌아 O(n^2)이 되어 시간초과가 될 것 같아 제곱근 방식을 이용하여 접근하였다. 아래의 제곱근 방식의 소수 찾기 알고리즘을 활용하였다.

백준 1978번 / 소수 찾기 / C++

다른분들의 결과를 확인해보니 필자가 작성한 코드는 메모리는 적게 사용했으나, 시간이 최대  약 15배까지 걸리는 방법으로 작성하여 아쉬웠다.

메모리를 이용하여 빠른 계산 방법인 무언가가 있다고 생각하게 되었다. 나중에 공부하자.

 

추가)

에라토스테네스의 체라는 알고리즘을 이용하여 구현하면 boolean 변수 배열을 사용하여 추가 메모리를 사용하는 대신 빠른 속도로 처리할 수 있다. 아래의 사진에서 속도가 192ms -> 12ms로 확실히 줄어든것을 볼 수 있다. 위 사진에서 최근 리스트 중 메모리는 가장 적게, 시간도 가장 적게 구현하였다.

에라토스테네스의 체 / C++

 

 

 

일반 구현방법

n부터 m까지 반복문을 돌면서 제곱근 방식으로 구현하였으며, 현재 값이 소수가 아닌경우, 출력하는 방식으로 간단하게 구현하였다.

#include <stdio.h>
 
int main()
{
    int m, n, i;
    bool b;
 
    scanf_s("%d %d", &m, &n);
 
    if (m == 1) m = 2;
 
    for (; m <= n; ++m)
    {
        b = 0;
 
        for (i = 2; i * i <= m; ++i)
        {
            if (m % i == 0)
            {
                b = 1;
                break;
            }
        }
 
        if (!b) printf("%d\n", m);
    }
}

 

에라토스테네스의 체를 이용한 구현방법

#include <stdio.h>
#include <math.h>
 
int main()
{
    bool* primes;
 
    int m, n;
 
    scanf("%d %d", &m, &n);
 
    primes = new bool[n + 1]();
 
    primes[1] = true;
 
    for (int i = 2; i <= sqrt(n); ++i)
    {
        if(!primes[i])
        {
            for (int j = i * 2; j <= n; j += i)
            {
                primes[j] = true;
            }
        }
    }
 
    for (int i = m; i <= n; ++i)
    {
        if (!primes[i]) printf("%d\n", i);
    }
}