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

문제 :1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 리턴하시오!

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

 

제한조건 

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

풀이 : 대학때도 많이 풀었고, 정처기 필기 알고리즘 부분에서도 다뤄서 쉽게 생각했다가...큰코를 다친 문제였다..

처음 문제를 풀었을때 정확성에서 3개틀리고,(시간초과) 효율성은0점을 받아... 소수 판별관련하여 다시 찾아보았다..

 

1. 기본 방법

  : 소수는 1과 자기자신만을 약수로 가지고있으니 2부터 n-1 까지 수로 나눠지면 안된다!

  : 이방법으로 생각없이 했다가 숫자가 커질경우 시간복잡도가 크게 올라가는걸 알게되어 다른 방법을 모색해야했다.

2. 제곱근

  : 소수이기에 필요 충분 조건은 주어진 수의 제곱근(sqrt)보다 크지않은 어떤 소수로도 나눠지지않는다.

  : 수가 수를 나누면 몫이 발생하게 되는데 몫과 나누는 수, 둘중 하나는 반드시 제곱근 이하이기 때문이다.

   

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;
    }
}

3. 에라토스테네스의 체

  : 소수의 배수는 약수로 무조건 소수를 포함하게된다 즉 절대 소수의 배수는 소수가 될 수 없다. 이것이 에라토스테네스의 체 이다. 2부터 시작하여 2의배수를 지우고, 지워지지않은 수중에서 3의 배수를 지워나가고 이를 반복하되 sqrt(n) (제곱근) 까지 진행 하여 지워지지않는 수들이 소수 인것이다!

public static int solution(int n)
{
    int answer = 0;
    bool[] list = Enumerable.Repeat<bool>(false, n).ToArray();
    list[0] = true;

    for (int i = 2; i <= Math.Sqrt(n); i++)
    {
        if (list[i -1] == true) continue;
        for (int j = i + i; j <= Math.Sqrt(n); j = j + i)
        {
            list[j - 1] = true;
        }
    }
    answer = list.Where(x => x == false).Count();
    return answer;
}

   

비교해봤을 시

주어진 수가 소수인지 아닌지 판별만 할경우는 제곱근을 사용하여 판단 하는것이 좋고

주어진 수까지 모든 소수를 구하기 위해서는 에라토스테네스의 체를 이용하는것이 좋다!