[백준,C++]1929: 소수 구하기

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

1929번: 소수 구하기

문제

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

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

출력

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

 

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int m, n;

int main(void) {
    cin >> m >> n;
    int size = n - m + 1;
    int* prime = new int[n + 1];
    prime[1] = 0;
    for (int i = 2; i < n + 1; i++) {
        prime[i] = 1;
    }

    //eratostheneses sieve
    for (int i = 2; i < n + 1;i++) {
        if (prime[i] == 0) {
            continue;// continue, break
        }
        else {
            for (int j = i * 2; j < n + 1; j += i) { //you don't always have to incerase the index by 1
                prime[j] = 0;
            }
        }
    }


    for (int i = m; i < n + 1; i++) {
        if (prime[i] != 0) {
            cout << i << '\n'; //\n is faster than endl;
        }
    }

    //cin >> n;
    return 0;
}

 

분명 내가 에라토스테네스의 채를 구현해서 성공했다고 생각했는데
런타임 에러가 나서 당황했다.....

여기서 중요한 기술, for문을 나는 1씩 증가 시키고 있었던거다......
그래서 처음 j(밑에서 부터 찾은 소수)의 인덱스도 i*2(어떤 소수의 2배는 소수가 아니니)
j=2*i라고 해주면 런타임을 아낄 수 있고 인덱스 증가도 i*3, i*4... 로 증가 할 수 있게 j+=i로 해주면 된다

시간 복잡도: O(nlogn) - 에라토스테네스의 채