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

프로그래머스 > 코딩테스트 연습 > 연습문제 > 소수 찾기

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

 

📒 문제

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를 반환

---

💻 소스코드

using System;
using System.Linq;

public class Solution {
    public int solution(int n) {    
        bool[] arr = Enumerable.Repeat(true, n+1).ToArray();
        for (int i = 2; i <= Math.Sqrt(n)+1; i++)
        {
            if (arr[i])
            {
                int j = 2;
                while(i * j <= n)
                {
                    arr[i * j] = false;
                    j++;
                }
            }
        }
        return arr.Where(w => w).Count()-2; // 0과 1 제외
    }
}

 

에라토스테네스의 체 알고리즘을 이용한 풀이이다.

오답노트의 풀이들이 시간초과로 오답이 나와 찾아보니 소수를 판별하는 알고리즘이 있어 적용해 보았다.

 

에라토스테네스의 체

에라토스테네스의 체 알고리즘은 2부터 자연수를 나열한 후 차례대로 처리를 하는데,

이때 처리란 자기를 제외한 배수들을 모두 제거하는 것이다.

예를들어 2부터 10까지의 숫자 중 소수를 찾는 다면 2부터 시작한다. 2를 제외하고 2의 배수 4, 6, 8을 제거한다.

다음 3을 제외하고 6, 9를 제거한다.

이런식으로 제거되지 않은 숫자들을 차례대로 처리하는데 모든 과정을 거치고 남은 수들이 소수이다.

 

코드를 풀이하면

찾고자하는 숫자n까지 만큼 길이의 bool배열을 만든다. (인덱스는 0부터 시작이므로 n+1)

bool은 모두 true를 담아둔다. (true는 소수)

 

0과 1을 제외하고 확인하기 위해서

2부터 n의 제곱근+1 까지 for문을 돌린다.

배열[i]가 true라면 처리를 시작한다.

j = 2를 선언하고 i*j가 10보다 작다면 배열[i*j]에 false를 대입하고 j++ 한다.

이 과정을 전부 거치면 소수에 해당되는 인덱스엔 true 아닌 경우엔 false가 된다.

 

마지막으로 배열에서 true인것만 뽑아 갯수를 세어주고 반환한다. 이때 0과 1을 제외해야해서 -2를 해주면 소수의 개수를 구할 수 있다.

 

오답 노트1

using System;
using System.Linq;

public class Solution {
    public int solution(int n) {
        return Enumerable.Range(2, n - 1)
                         .Where(w1 => Enumerable.Range(2, w1 / 2 - 1)
                                                .Where(w2 => w1 % w2 == 0)
                                                .Count() == 0)
                         .Count(); 
    }
}

 

2 부터 원하는 숫자 n까지 시퀀스를 만들고 (Range)

각 요소를 다시 2부터 요소/2크기만큼의 Range를 만들고(Range) 해당 요소w2로 w1을 나눴을때 나머지가 0이면 소수임으로 소수인 값만 추출해서(Where) 개수를 세주고(Count) 개수가 0인 값들만 추출해주었다(Where) 그리고 그 개수를 세주면 소수의 개수를 알수있다.

 

하지만 해당 코드는 너무 오래걸리므로 시간 초과로 실패가 된다.

 

 

오답노트2

using System;

public class Solution {
    public int solution(int n) {
        int answer = 0;
        for(int i = 2; i <= n; i++)
        {
            bool isDecimal = false;
            for (int j = 2; j <= Math.Sqrt(i); j++)
            {
                if (i % j == 0) 
                {
                    isDecimal = true;
                    break;
                } 
            }

            if (!isDecimal) answer++;
        }
        
        return answer;
    }
}

 

오답노트1의 흐름에서 소수가 아닌게 판단이 되면 break로 탈출 하였다.

오답노트1 보단 빠르게 처리되었지만 아직 부족해 마지막 에라토스테네스의 체 알고리즘을 찾게 되었다.

 

※ 참고 사이트

에라토스테네스의 체 : https://velog.io/@changhee09/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%86%8C%EC%88%98%EC%9D%98-%ED%8C%90%EB%B3%84-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4

---

관련 포스팅

[C#] Enumerable 클래스 (Linq)