백준 1929: 소수 구하기(C++)

문제 링크 : http://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

 

 

문제

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

입력

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

 

출력

 

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

 

 

 

해설

어떤 수 n이 있을 때 2~n-1까지 모든 수를
n과 나눠보면서 나머지가 0인 수가 존재한다면
n은 소수가 아니다.

이 문제의 방법은 시간복잡도가 n^2인데
문제에서 주어지는 n은 100만으로
무조건 시간초과가 난다.

#include<iostream>
using namespace std;
int main(void)
{
    int n;
    cin>>n;
    for(int i=2; i<n; i++)
    {
        if(n%i==0)
        {
            cout<<"이 수는 소수가 아닙니다.\n";
            return 0;
        }
    }
    cout<<"이 수는 소수입니다.";
}
//시간복잡도가 n^2인 코드

 

 

그래서 다른 방법을 찾아야 하는데
그것이 바로 '에라토스테네스의 체'이다.
구현 방법은 쉽다.
일단 모든 숫자를 적는다. 그리고 소수가 아닌수를 지워줄 건데
1을 일단 지워준다.(예외)

그리고 2를 볼건데 2를 제외한 2의 배수는 모두 소수가 아니므로
지워준다.

그리고 3도 마찬가지로 3을 제외한 3의 배수도 모두 지워준다.

4는 이미 2의 배수를 지울 때 지워졌다. 
그리고 4의 배수는 모두 2의 배수와 같으므로 그냥 넘어간다.
(코드에서는 간결함을 위해 안 넘어감, 넘어가면 코드가 조금 더 빨라짐)

이를 n-1까지 반복한다.
마지막으로 지워지지 않은 수들을 출력해주면 된다.

 

 

코드

#include<iostream>
using namespace std;
int main()
{
    int m,n;
    cin>>m>>n;
    int a[n+1];
    fill(a,a+n+1,0);
    a[1]=1;
    for(int i=2; i<n; i++)
    {
        for(int z=i+i; z<=n; z+=i)
        {
        	/* i가 이미 지워졌을 때 넘어가는 코드
        	if(a[i]==1)
            	   break;
           	*/
           a[z]=1;
        }
    }
    for(int i=m; i<=n; i++)
    {
        if(a[i]==0)
            cout<<i<<'\n';
    }
}