[프로그래머스][C++] 소수 찾기

 

https://programmers.co.kr/learn/courses/30/lessons/12921

코딩테스트 연습 - 소수 찾기

 

글쓴이의 답

개인적인 풀이 임으로

이것보다 더 좋은 알고리즘은 많음...

이렇게도 풀이하는구나.. 공유하기 위해 올림...

#include <string>
#include <vector>
#include <memory.h>
#include <iostream>

using namespace std;

int solution(int n) {
    int answer = 0;
    
    bool *check = new bool[n+1];
    memset(check, true, sizeof(bool)*(n+1));
    
    for (int i = 2; i * i <= n; i++) {
		if (check[i]){            
            for (int k = i * i; k <= n; k += i){                
        		check[k] = false;
            }
        }                
	}
    for(int i =2; i<= n; i++){
        if(true == check[i]){
            answer++;
        }
    }
    
    delete[] check;
    
    return answer;
}

꾸준히 하다보면 실력이 늘겠지..