[프로그래머스] - 소수 찾기(C#)

소수 찾기

오늘은 "소수 찾기" 문제를 풀어보겠습니다. 이제 정답률도 점점 낮아져 61퍼가 되었습니다. 곧 60퍼 보다 낮은 정답률을 가진 문제들이 등장할 것입니다. 문제 살펴보겠습니다.

 

문제 설명

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

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

 

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

 

입출력 예

n	result
10	4
5	3

 

입출력 예 설명

입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

 

시작 코드

public class Solution {
    public int solution(int n) {
        int answer = 0;
        return answer;
    }
}

 

나의 풀이

using System;
public class Solution {
    public int solution(int n) {
        int answer = 0;
        for (int i = 2; i <= n; i++) { if (isPrime(i)) answer += 1; }
        return answer;
    }

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

 

코드 분석

int형 자연수 n이 주어지며 코드가 시작됩니다. for문을 i =  2부터 n보다 작거나 같을 때까지 돌리며 그 안에는 if문이 있습니다. if문에서는 isPrime(i)가 있으면 answer에 1을 더하라고 되어있는데, isPrime은 solution밖에 bool타입 함수로 만들어져 있습니다. 매개변수로 n을 받으며 int형 nr을 선언하고 n을 Math.Sqrt를 통해 제곱근을 구한 다음 int형으로 바꿔서 넣어줍니다. 그리고 2부터 nr보다 작거나 같을 때까지 동작하는 for문에서, 만약 n을 i로 나눈 나머지가 0이라면 false를 리턴하고 그게 아니면 true를 리턴하게 합니다. 이제 다시 위로 올라가서 for문에서 넘겨준 i를 n으로 받아 계산한 값이 true라면 answer를 더해줍니다. 그리고 answer값을 리턴하고 코드가 종료됩니다.

 

풀이 설명

이번 문제 설명은 상당히 간결합니다. 문제가 원하는 답은 n이 주어질 때, 1부터 n까지 존재하는 소수의 개수입니다.

어차피 1은 무조건 나눠지므로, 제외한 2부터 모든 for문이 돌아가는 것입니다. isPrime함수는 사용자가 직접 만든 새로운 함수인데, bool타입의 반환형을 가지는 함수입니다. nr로 매개변수로 받은 n(i)의 제곱근을 만들어 for문을 따로 돌리고, 해당 함수의 for문에서의 n(i)를 i로 나눈 나머지가 0이면 소수가 아닌 것입니다. 그 외에는 전부 소수판정으로 true를 반환합니다. isPrime을 통해 소수판단이 되었으니 answer를 올리고 모든 과정이 끝나면 answer를 반환하여 소수의 개수를 구합니다.

 

<NEXT>

오늘은 "소수 찾기" 문제를 풀어보았습니다. 다음에는 "덧칠하기" 문제를 다뤄보도록 하겠습니다. 감사합니다.