프로그래머스 LV1 C++ 소수찾기 풀이

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

 

코드 풀이

이 문제는 다른 문제들과 다르게 시간복잡도에 주의해야했다.

처음에 이중 for문을 쓰면서 이거 안될거 같다 했는데 혹시나가 역시나

 

소수를 찾는 알고리즘은 꽤 많이 알려져 있고 인터넷검색에도 있기에 어렵진 않았다.

내가 참고한 사이트는 아래이다.

[알고리즘] 소수(Prime Number) 구하기 - 에라토스테네스의 체 (Java) (tistory.com)

[알고리즘] 소수(Prime Number) 구하기 - 에라토스테네스의 체 (Java)

 

내가 이해한대로 간단하게 작성 해보고자 한다.

소수 정의는 넘어가고 코드 설명만 할 것이다.

bool isPrime(int n){
    for(int i = 2; i*i<=n; i++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

이것이 내가 사용한 식이다.

가장 단순한 식은 분명

bool isPrime(int n){
    for(int i = 2; i<=n; i++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

이것일 것이다. 위의 코드와의 차이첨은 i를 제곱했느냐 아니냐의 차이

이 차이 덕분에 N인 복잡도가 N½로 줄어 들게 된다.

백문이 불여일견 몇가지를 예시로 들어 해보겠다.

 

ex) n = 5일 경우

i = 2 :  2*2<= 5가 참이므로 실행

5는 2로 나뉘지 않으므로 다음 수로

i = 3 : 3*3 <= 5가 거짓이므로 for문을 끝내게 되고 

참을 리턴하게 된다.

 

ex) n = 15일 경우

i = 2 : 2*2 <= 15가 참이므로 실행

15는 2로 나뉘지 않으므로 다음수로

i = 3 : 3*3 <= 15가 참이므로 실행

15는 3으로 나뉘므로 for문을 끝내고 거짓을 리턴하게된다.

 

ex) n = 7일 경우

i = 2 : 2*2 <= 7이 참이므로 실행

7은 2로 나뉘지 않으므로 다음수로

i = 3 : 3*3 <= 7 이 거짓이므로 for문을 끝내게 되고

참을 리턴하게 된다

 

위의 예시들을 보면 i가 num만큼 반복하지 않았음에도 값을 반환한다는 걸 알 수 있다.

자세한 원리는 위에 참고한 링크를 보길 바란다.(어렵..)

 

암튼 위를 알고 코드를 짜보자

먼저 보기 편하게 사용자 함수로 소수 판단문을 작성하였다.

bool isPrime(int n){
    for(int i = 2; i*i<=n; i++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

2에서부터 n까지 실행하는 for문을 작성하고 isPrime에 i값을 전달하면 각 수에대해 판단하게 된다.

맞다면 true를 반환하기에 answer값이 증가한다.

int solution(int n) {
    int answer = 0;
    
    for(int i = 2; i <= n; i++){
        if(isPrime(i)){
            answer++;
        }
    }
    return answer;
}

 

전체코드

#include <string>
#include <vector>

using namespace std;

bool isPrime(int n){
    for(int i = 2; i*i<=n; i++){
        if(n % i == 0){
            return false;
        }
    }
    return true;
}

int solution(int n) {
    int answer = 0;
    
    for(int i = 2; i <= n; i++){
        if(isPrime(i)){
            answer++;
        }
    }
    return answer;
}