[C++] 백준 1929번 : 소수 구하기 (S2)

#문제

www.acmicpc.net/problem/1929

1929번: 소수 구하기

#풀이 & 학습한 내용

에라토스테네스의 체를 이용해야 하는 문제이다. supremo7.tistory.com/115에서 푼 것처럼 하나하나의 수가 소수인지 판정(시간복잡도 O(√n))한다면, 총 시간복잡도는 O(n√n)이 되고, 이때 worst case에서 1,000,000*1,000=1,000,000,000으로 1초(1억)인100,000,000을 넘으므로 불가능하다. 이때, 소스코드 10행에서처럼 i*i<=1000000까지만 고려하면 된다. 그리고 소스코드 12행에서 j++이 아닌 j+=i임을 주의하자.

 

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
bool prime[1000002];//지워졌으면 true(1), 소수인게 false(0)
 
int main(void) {
    prime[1] = true;
    for (int i = 2; i*i <= 1000000; i++) {
        if (prime[i] == false) {
            for (int j = i * 2; j <= 1000000; j+=i) {
                prime[j] = true;
            }
        }
    }
 
    int a, b;
    cin >> a >> b;
    for (int i = a; i <= b; i++) {
        if (prime[i] == false) {
            cout << i << '\n';
        }
    }
}

 

github.com/HoYoungChun/BOJ_algorithm/blob/master/Math/BOJ_1929.cpp

HoYoungChun/BOJ_algorithm