[BOJ/백준] 1929 소수 구하기

● [문제번호 1929] 소수 구하기

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

● 알아야 할 것

: vector 자료구조와 메소드

: 에라토스테네스의 체

 

● 풀이 과정

: M부터 N까지 하나씩 소수인지 확인하는 풀이를 이용하면 '시간 초과' 결과를 가져온다.

: 에라토스테네스의 체를 이용하여 소수를 만들어 놓은 다음

범위에 맞는 소수들을 출력하면 된다.

 

● 주의 할 것

: hidden case에 M값이 1인 경우도 있으니 에라토스테네스의 체를 만들 때 기본값 설정을 꼭 해야한다.

 

● 참고 할 것

: 에라토스테네스의 체

2부터 (범위의 끝)의 제곱근까지 각 소수의 배수들을 모두 합성수 처리하면

원하는 범위 내 소수만 남는다.

 

아래 링크에 있는 이미지입니다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// 에라토스테네스의 체 만들기 위한 vector
vector<bool> v;
int M, N;

// 에라토스테네스의 체를 이용한 소수찾기
void check_decimal()
{
    // 기본값 설정
    v[0] = false;
    v[1] = false;
    
    // 해당 범위의 제곱근까지 확인하면 된다
    for(int a = 2; a < sqrt(N + 1); a++)
    {
        // 소수인 경우
        if(v[a] == true)
        {
            // 소수의 배수는 합성수로 체크
            for(int b = 2; a * b < N + 1; b++)
                v[a * b] = false;
        }
    }
}

// M 부터 N 까지 에라토스테네스의 체를 확인하여 소수를 출력한다
void print_MN_decimal()
{
    for(int i = M; i <= N; i++)
        if(v[i] == true)
            cout << i << "\n";
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> M >> N;
    
    // index를 소수판별값으로 하기에 N + 1개 할당
    v.assign(N + 1, true);
    
    // 에라토스테네스의 체 만들기
    check_decimal();
    
    // 소수 출력하기
    print_MN_decimal();
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [300 - 수학 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	10430	나머지	https://pirateturtle.tistory.com/180
2	2609	최대공약수와 최소공배수	https://pirateturtle.tistory.com/181
3	1934	최소공배수	https://pirateturtle.tistory.com/182
4	1978	소수 찾기	https://pirateturtle.tistory.com/183
5	1929	소수 구하기	https://pirateturtle.tistory.com/184
6	6588	골드바흐의 추측	https://pirateturtle.tistory.com/185
7	10872	팩토리얼	https://pirateturtle.tistory.com/186
8	1676	팩토리얼 0의 개수	https://pirateturtle.tistory.com/187
9	2004	조합 0의 개수	https://pirateturtle.tistory.com/188