[C#] 소수 찾기

소수 찾기

문제 설명

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

풀이

초기 접근

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

• 가장 먼저 할 수 있는 생각은 해당 범위의 모든 숫자들에 대해서 소수인지 여부를 판단하는 함수를 돌리는 것
• 그러나 시간복잡도가 지나치게 높은 효율적이지 않은 방법이라고 생각해 접근 방식을 변경

리스트에서 숫자를 제거

• 이후 생각한 방법은 n까지의 범위의 숫자를 담은 리스트를 구성

• 해당 리스트를 처음부터 순회하며 각 인덱스의 해당하는 값의 배수를 리스트에서 제거

  Ex) nums = [2,3,4,5,6...] 인 리스트가 있다고 가정할 때
  i) nums[0] = 2
  n범위에서 2의 배수에 해당하는 값들을 리스트에서 제거
  nums = [3,5...]
  ... 3의 배수에 해당하는 숫자를 제거...5의 배수에 숫자에 해당하는 숫자를 제거

• 그렇게 제거하다가 확인하는 인덱스가 리스트의 마지막이거나 벗어났을 때 해당 실행을 종료하여 소수만 남은 리스트를 만들수 있지 않을까 생각함

	private void LeavePrimeNumber(int n, int index, ref List<int> numbers)
    {
    
    	if(index >= numbers.Count) return;
    
        int checkNumber = numbers[index];
        
        for (var i = 2; i <= n / checkNumber; i++)
        {            
            if(numbers.Contains(i * checkNumber))
                numbers.Remove(i * checkNumber);
        }
        
        int nextIndex = index + 1;
        
        LeavePrimeNumber(n, nextIndex, ref numbers);
    }

• 해당 로직을 재귀 함수를 통해 구현하려고 했으나 리스트에서 해당 숫자가 있는지 확인하고, 제거하는 과정에서 비용이 크게 발생함을 인식

+ 에라토스테네스의 체

• 어떻게 추가적으로 검사 범위를 줄일 수 있을까 조사하는 과정에서 에라토스테네스의 체라는 개념을 학습
• 소수를 찾고자 할 때 주어진 숫자가 n이라면 n의 제곱근보다 작은 범위의 숫자에 대해서 배수인지 확인하는 것으로 특정 범위에 있는 숫자를 제거할 수 있다는 개념
• 해당 방식을 활용해 검사 범위를 n의 제곱근 이하 범위로 줄일 수 있었음

최종 풀이

public class PrimeNumberFinder
{
    public int Solution(int n) {
        bool[] isPrime = new bool[n];
        
        for (var i = 2; i <= Math.Sqrt(n) + 1; i++)
        {
            CheckPrimeNumber(n,i, ref isPrime);
        }
        
        int answer = 0;

        foreach (var result in isPrime)
        {
            answer = result ? answer : answer+1;
        }
        
        return answer-1;
    }
    
        private void CheckPrimeNumber(int n, int checkNumber, ref bool[] isPrime)
    {
        for (var i = 2; i <= n / checkNumber; i++)
        {
            int targetNumber = checkNumber * i;
            
            if (checkNumber * i <= isPrime.Length && !isPrime[targetNumber-1])
            {
                isPrime[targetNumber-1] = true;
                Console.WriteLine(targetNumber);
            }
                
        }
 }

• 숫자 리스트를 만들어 배수인 숫자를 찾고 제거하는 과정을 n 크기를 가진 bool 배열로 변경해 배수인 숫자의 인덱스 위치의 값을 변경하는 것으로 단순화
• Math.Sqrt(n)를 활용해 배수를 찾는 범위를 줄여 문제를 해결