에라토스테네스의 체

소수를 찾는 알고리즘이다. 이렇게 빠를줄은 생각도 안하고 있었는데.... 엄청 빠르다

 

<코드>

int prime_Num(int n) {
    int cnt = 0;
    vector<bool> check(n+1, 1);
    
    for(int i = 2; i <= n; i++) {
        for(int j = i+i; j <= n; j += i) {
            if(check[j] == 0) continue;
            else check[j] = 0;
        }
    }
    
    for(int i = 2; i <= n; i++) {
        if(check[i] == 1) {
        	cnt++;
        	cout << i << endl;
		}
    }
    
    return cnt;
}

 

<설명>

2부터 시작한다.

하나씩 키워가면서 2를 제외한 모슨 배수를 check해준다.

이와 같은 방법으로 3, 4, 5, .... 계속 해나가면 결국에는 소수를 제외한 모든 수들은 체크가 될것이고, 소수만 결국 남게 된다.

흠....... 생각보다 엄청 빨라서 좀 당황하긴 했지만, 새로운걸 배웠다는거에 만-족ㅎㅎㅎㅎㅎㅎㅎㅎ

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

쓰면서 생각드는건데 3, 4, 5,.... 하나씩 키워가는데 키워갈 때 그 수를 check를 확인했을 때 이미 check 된거면 굳이 그 숫자를 할 필요가....?? 수정해보면 다음과 같다.

int solution(int n) {
    int answer = 0;
    vector<bool> check(n+1, 1);
    
    for(int i = 2; i <= n; i++) {
    	if(check[i] == 0) continue;
        for(int j = i+i; j <= n; j += i) {
            check[j] = 0;
        }
    }
    
    for(int i = 2; i <= n; i++) {
        if(check[i] == 1) {
        	answer++;
		}
    }
    
    return answer;
}

나는 몽총이.... 더 좋아졌잖아 ㅠㅠㅠㅠㅠ