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

문제 설명

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

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

 

제한 사항

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

 

프로그래머스

 

 

1차 풀이 코드 실패 (에라토스테네스의 체로 풀어봄)

 public class Program
{
    static void Main(string[] args)
    {
        List<int> primeList = new List<int>();
        List<int> list = new List<int>();

        for (int i = 2; i < 1000000; i++)
        {
            if (GetPrime(i))
            {
                primeList.Add(i);
            }
        }

        int n = 10;

        for (int i = 2; i <= n; i++)
        {
            list.Add(i);
        }

        list.RemoveAll(x => IsPrime(2, x) == false);
        list.RemoveAll(x => IsPrime(3, x) == false);
        list.RemoveAll(x => IsPrime(5, x) == false);
        list.RemoveAll(x => IsPrime(7, x) == false);
        list.RemoveAll(x => IsPrime(11, x) == false);

        Console.WriteLine($"list count : {list.Count}");
    }

    private static int gcd(int n, int m)
    {
        while(m > 0)
        {
            var r = n % m;
            n = m;
            m = r;
        }

        return n;
    }

    private static bool GetPrime(int num)
    {
        for (int i = 2; i <= 1000000; i++)
        {
            if (num == i) continue;
            if (num < i) return true;

            if (num % i == 0)
            {
                return false;
            }
        }

        return true;
    }

    private static bool IsPrime(int m, int num)
    {
        if (m == num) return true;

        if (num % m == 0)
        {
            return false;
        }

        return true;
    }
}

 

2차 풀이 코드 실패 (2에서 n / 2까지 약수인지 확인)

using System.Collections.Generic;

public class Solution {
    public int solution(int n) {
        List<int> list = new List<int>();

        for (int i = 2; i <= n; i++)
        {
            if (IsPrime(i))
            {
                list.Add(i);
            }
        }
        
        return list.Count;
    }
    
    private static bool IsPrime(int n)
    {
        for (int i = 2; i <= n / 2; i++)
        {
            if (n == i) continue;

            if (n % i == 0)
            {
                return false;
            }
        }

        return true;
    }
}

 

시간 복잡도가 선형 시간으로 늘어나서 효율성 테스트 실패

 

O(n)

단순하게 n까지 확인해서 해당 수로 나눠지는 지를 확인해본다.당연하게도 실패

 

O(n/2)

2차 시도는 n/2만큼까지 확인해서 해당 수로 나눠지는 지를 확인해본다. 이때 당시에는 O(n)은 O(n/2)와 시간 복잡도가 동일하다는걸 알지 못했다. 

 

O(N) vs O(2N): Are They Same? If yes then How?

 

3차 풀이 코드 실패 (2에서 Sqrt(n)까지 약수인지 확인)

using System;

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

        for (int i = 2; i <= n; i++)
        {
            if (IsPrime(i))
            {
                answer++;
            }
        }
        
        return answer;
    }
    
    private static bool IsPrime(int n)
    {
        for (int i = 2; i <= Math.Sqrt(n); i++)
        {
            if (n % i == 0)
            {
                return false;
            }
        }

        return true;
    }
}

 

O(√n)

n / 2로 최적화를 시도했지만 효율성에서 실패

IsPrime 함수 내에서 i의 제곱근보다 클때까지만 진행하도록 수정

 

풀이 코드 (2에서 제곱근까지 약수인지 확인)

using System;

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

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

        return true;
    }
}

 

i * i 로 비교하든 Sqrt(n)까지 비교하든 동일하거라고 생각했지만 코드 효율성 측면에서 Math.Sqrt가 더 느리다.

 

• i * i <= n
• i <= Math.Sqrt(n) 

 

O(log n)

i * i  <= n은 log n의 복잡도로 동작한다.

 

i^2 <= n이므로 log_i n = 2로 표현이 가능하다. 베이스를 생략하고 양변을 2로 나눠주면 log n/2로 작성이 가능하다. 이때 지수가 아닌 수를 생략하므로 log n으로 표현된다.

sqrt(n)의 복잡도가 log n보다 높다.

 

풀이 코드 (에라토스테네스의 체)

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int solution(int n) {
        bool[] isPrime = Enumerable.Repeat(true, n + 1).ToArray();

        for (int i = 2; i * i <= n; i++)
        {
            if (isPrime[i])
            {
                for (int j = i * i; j <= n; j += i)
                {
                    isPrime[j] = false;
                }
            }
        }

        List<int> list = new List<int>();

        for (int i = 2; i <= n; i++)
        {
            if (isPrime[i])
            {
                list.Add(i);
            }
        }

        return list.Count();
    }
}

 

O(n log log n) 의 복잡도를 가진다.

함께 읽으면 좋은 글

O(log n) 시간 복잡도란 무엇인가?

 

두 조건에 대해서 정리한 글

Which is more efficient inside a loop condition, i<sqrtN (pre-calculated) or i*i<N, in C++?