백준 1929번 (C++)

www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

<답안>

#include <iostream>
using namespace std;
int main()
{
    int array[1000001];
    int m,n;
    cin>>m>>n;
    
    array[1] = -1;
    for(int i=2; i<=n; i++)
    {
        for(int j=2; j * i <= n; j++)
        {
            array[j*i] = -1;
        }
    }
    for(int i=m; i<=n; i++)
    {
        if(array[i] != -1)
            cout<<i<<"\n";
    }
    
    return 0;
}

 

<설명>

흔히 소수를 판별하는 알고리즘인 2부터 숫자-1까지 나눠보는 식으로는 시간초과가 뜨는 문제였다

그래서 소수판별에 다른 알고리즘이 있나 검색을 해보았더니

"에라토스테네스의 체" 알고리즘을 사용하면 되는 문제였다

 

간단히 알고리즘을 설명하자면, 어떤 수이던 간에 그 수의 "모든배수는 소수가 아니다" 라는 점을 이용하는 것이였다

그래서 간략히 곱해질 대상숫자 i를 1부터 끝숫자인 m까지 돌리고,

곱해질 i를 곱할숫자 j를 2부터 증가시키며 계속 곱해본다

그러다가 i와 j를 곱한값이 m을 넘어버리면 곱해질 숫자 i를 다음값으로 올리는 식이다

 

그렇게해서 i 곱하기 2부터 곱한 배수들은 소수가 아니므로 -1로 판정을 넣으면

결국 -1값이 아닌 수들이 소수인 셈이다

그 배수자체를 인덱스로 하여 array[i * j] = -1 로 체크를 하였다

 

그래서 결론적으로 -1이 아닌경우 그 숫자를 출력하면 된다