소수구하기 문제였습니다.
소수를 구하는 알고리즘에서는 요구하는 조건이
- 특정수의 소수판별
- 범위 소수 개수 판별
크게 이 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()); // 출력
}
