프로그래머스 소수찾기

 

n값입력이주어지면

1부터 n까지 소수의 개수를 출력하는 문제다

 

 

소수판별을 에라토스테네스의 체로 풀어야 통과가되는것같다

에라토스테네스 체가 좀 오래간만이라 헷갈렸는데

 

일단 n이 입력되면

동적할당으로 n+1만틈 bool 배열을 만들어주고

모두 true로 초기화한다

false는 소수가아니다 라는 의미고

true는 소수다 라는 의미다

 

n이 만약에 20이라고하면

4*4<20

5*5>25이므로

1~4까지만 반복문을돌며(1은 사실돌필요가없다)

2~4까지만 반복문을 돌며

각각의 배수를 

2->2,4,6,8,10,12,14,16,18,20

3->3,6,9,12,15,18 을 false로해줌

4는 소수가아니므로 반복문안돔(왜냐하면 2가 먼저 다 표시해주었기때문에)

4의배수 4,8,12,16,20을 돌필요가없음

 

그렇게 해서 2,3,5,7,11,13,17이 살아남게된다

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(int n) {
    bool* arr=new bool[n+1];
    for(int i=0; i<n+1; i++){
        arr[i]=true;       //소수면 true 소수아니면 false
    }
    int answer = 0;

        for(int j=2; j*j<n; j++){
            if(arr[j]==true){
                for(int k=j*2; k<=n; k=k+j){
                    arr[k]=false;
                }
            }
        }
  
    for(int i=2; i<=n; i++){
        if(arr[i]==true){
            answer++;
        }
    }
return answer;
}

 

저번엔 코드를 보고 베꼈는데

이번에는 내 생각으로 다시 풀어낸게 좀 기분이 좋았다