# 백준 : 소수 구하기(1929)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/edit/master/bj_1929_Eratosthenes'%20sieve)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int main(void) {
    int start, end;
    int arr[1000001];
    //int number, index;
    cin>>start;
    cin>>end;
    
    arr[0] = 1;
    arr[1] = 1;
    
    for(int i=2; (i*i)<=end; i++) {
        for(int j=0; i*(i+j)<=end; j++) {
            arr[i*(i+j)] = 1;
        }
    }
    
    for(int i=start; i<=end; i++) {
        if(arr[i] == 0) cout<<i<<'\n';
    }
    return 0;
}

풀이

진짜 겁나 짜증이나는데 왜 계속 시간초과가 나는지 도저히 모르겠지만, 우선 내 실력이 부족하다고 생각하고 자그마치 2시간 이상을 매달렸는데 왜 계속 시간초과가 나는지 도무지 모르겠다.
각설하고, 무려 정답률 30%에 육박하는 엄청난 문제라서 패기넘치게 도전했다. 정답입니다!가 뜨면 블로그에 올리려고 했지만 그러다가는 내 속이 먼저 터져버릴것 같아서 우선 블로깅한다. 
'에라토스테네스의 체'는 소수를 구하는 굉장히 효율적인 방법 중 하나로 소개된다. 
자세한 설명은 이곳을 참조하면 된다.
또 다른 설명이 필요하다면 이곳도 참조하면 된다.
소수의 배수를 각각 지워내다보면 결국 남는건 소수뿐이라는 굉장히 단순한 방법이다. 
문제는 중복되는 수가 존재하기 마련(15는 3의 배수이면서도 동시에 5의 배수)인데, 이 부분이 알고리즘 계산에는 치명적일 수 있다.
친절하게도 이 부분은 조금만 생각해보면 알 수 있는데, 우선 내가 사용한 계산식은 다음과 같다.
숫자 n에 대해서는 n*n + n*i (0<=i<=max)로 구하면 된다.
즉 숫자 3이 주어졌을 때, 계산은 3*3+0, 3*3+3, 3*3+3*2 등으로 하면된다.

이 와중에 슈밤 답을 맞췄다!! endl를 쓰면 안된다.
endl... endl.... '\n'을 써야 한단다. 알려주신 분 너무 감사해요..