[알고리즘] 소수 구하기

백준 1929번에서 파생되었습니다.

 

---

 

소수구하기 문제였습니다.

 

소수를 구하는 알고리즘에서는 요구하는 조건이

1. 특정수의 소수판별
2. 범위 소수 개수 판별

크게 이 2가지로 나뉜다고 볼 수 있습니다.

 

 

<1. 특정수의 소수판별>

 

어떤수 n이 주어졌을때 소수를 판별하는 방법으로

흔히 n의 제곱근까지 비교하여 약수의 개수를 세는 방법입니다.

 

기준 1) 소수는 약수를 1과 자기자신 밖에 가지지않기 때문에 항상 약수의 개수가 2개입니다.

• 1의 경우  :  1은 약수로 1밖에 가지지 않습니다. 약수의 개수가 1개이기 때문에 소수가 아닙니다.
  • 편의상 약수가 1개라 소수가 아니라는거지, 정말 1이 소수인 이유가 약수가 1개라서는 아닙니다.
• 3의 경우  :  3은 약수로 1, 3을 가집니다. 약수의 개수가 2개이기 때문에 소수입니다.
• 8의 경우  :  8은 약수로 1, 2, 4, 8을 가집니다. 약수의 개수가 4개이기 때문에 소수가 아닙니다.

 

기준 2) 약수는 원래의 숫자될 수 있는 약수쌍을 가지고 있습니다.

 

1부터 n까지 비교할 필요없이 1부터 n의 제곱근까지만 비교하면 됩니다.

 

약수는 한개만 찾는다면 ( n / 약수 )를 통해 다른 약수를 찾을 수 있습니다.

1과 자기자신도 1 * n = n이라는 숫자쌍이라고 볼 수 있습니다.

예외로 25의 5 * 5처럼 숫자쌍이 겹치는 경우도 있지만 제곱근까지 비교하면 자연스럽게 포함됩니다.

 

기본구현

 

int isPrime(int n) 
{
    int sqt = MathF.Sqrt(n); // 제곱근
    for(int i = 2; i <= sqt; i++) // 1을 제외하고 2부터
    { 
        if(n % i == 0) // 1과 n이 비교대상에서 제외되었으므로 하나라도 통과한다면 
            return 0;  // 소수가 아닙니다.
    }
    
	return 1; // 소수입니다.
}

 

시간복잡도는 O(√n)입니다.

 

<2. 범위 소수 개수 판별>

 

범위내의 숫자들중에서 소수가 몇개인지 요구하는 문제입니다.

이때는 '에라토스테네스의 체'를 사용해서 해결합니다.

 

'에라토스테네스의 체'란 소수의 배수들을 제거하여 약수만 살리는 방법입니다.

다음 살아남은 숫자의 배수를 지워가는 식으로 진행됩니다.

에라토스테네스의 체

처음엔 모두 살아있으니 그중 첫번째인
2는 살리고 2의 배수를 다 지웁니다.
2 다음으로 살아남은 수 3은 살리고 3의 배수를 다 지웁니다.
3 다음으로 4는 2의 배수로 지워버렸으니 건너뜁니다.
3 다음으로 살아남은 수 5는 살리고 5의 배수를 다 지웁니다.
.... 이런식으로 끝까지 진행하고 살아남은 숫자들은 소수입니다.

 

기본구현

 

void eratostenes(int min, int max)
{
    bool[] Len = new bool[max + 1]; // 조건이 범위로 주어지더라도 max값을 기준으로 배열을 만듭니다.

    for (int i = 2; i <= max; i++) // 최소 소수 2부터 max까지
    {
        if (Len[i] == false) // 해당수가 지워져 있다면 건너뜁니다
        {
            Console.WriteLine(i); // 소수를 출력해주고
        
            for (int j = 1; j * i <= mx; j++) // 방식에 따라서 2부터 시작하여 소수를 살릴수 있습니다.
                Len[i * j] = true; // 배수를 다 지웁니다.
        }
    }
}

 

시간복잡도는 O(nloglogn)입니다.

 

에라토스어쩌고 알고리즘은 테스트케이스 최대 1,000,000정도로 제한적이라고 합니다.

 

---

 

백준 시간초과 극복용

 

void eratostenes(int mn, int mx)
{
    mn += (mn == 1) ? 1 : 0;

    StringBuilder sb = new StringBuilder(); // 출력시간 조절위해 StringBuilder사용
    
    bool[] Len = new bool[max + 1];
    
    int mid = (int)MathF.Sqrt(max) + 1; // StringBuilder로 저장 출력 -> 즉시 출력X
    for (int i = 2; i < mid; i++)     // 그렇게 때문에 최대값의 제곱근까지만 비교해도 충분합니다.
    {
        if (Len[i] == false)
        {
            for (int j = 2; j * i <= max; j++)
                Len[i * j] = true;
        }
    }
    
    for (int i = min; i <= max; i++)
    {
        if (Len[i] == false)
            sb.AppendLine($"{i}"); // 범위 안의 판별된 소수들을 StringBuilder에 삽입
    }

    Console.WriteLine(sb.ToString()); // 출력
}