소수 구하기, 에라토스테네스의 체

 

1. 가장 기본적인 방법

• 자연수 x가 소수인지 판별하기 위해서 생각할 수 있는 가장 간단한 방법
• x를 2 ~ n-1까지의 모든 수로 나누어 보고, 나누어 떨어지는 수가 존재하는지 확인하는 것
• O(n)의 시간복잡도를 가지고 있다

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

 

 

2. 제곱근을 이용하는 방법

• x를 2 ~ √x까지의 모든 수로 나누어 보고, 나누어 떨어지는 수가 존재하는지 확인하는 것
• O(√n)의 시간복잡도를 가지고 있다

bool IsPrime(int num) 
{
    int sqrtNum = (int)Math.Sqrt(num); 
    for (int i = 2; i <= sqrtNum; ++i) 
    {
        if (num % i == 0)
            return false; 
    }
    return true; 
}

왜 제곱근이 기준인가?

 '소수인지 판별할 자연수 x의 제곱근 √x'를 기준으로 'x의 약수들의 곱'은 대칭이 된다

= x의 약수는 무조건 √x의 범위에 존재한다

 

예시

 x = 24, √x =√24 를 기준으로 할 때,

2 * 12     ,     3 * 8     ,     4 * 6     |     √24 * √24     |     6 * 4     ,      8 * 3     ,     12 * 2

따라서 x가 소수인지 파악하려면 제곱근 이하의 수까지만 검사해도 괜찮다

 

 

---

 

 

자연수 x 이하의 모든 소수를 찾는 방법

에라토스테네스의 체

• 고대 그리스 수학자 에라토스테네스가 만든 '소수를 찾는 방법' (체로 치듯 수를 걸러낸다)
• O(nloglogn)의 시간복잡도를 가진다

void PrintAllPrimeLowerThanA(int a)
{
    bool[] primes = new int[a + 1];
    
    //처음엔 모든 수가 소수인 것으로 초기화
    for (int i = 0; i < arr.Length; ++i)
    {
        primes[i] = true;
    }
    
    //2부터 a의 제곱근까지 모든 수를 확인하며
    for (int i = 2; i <= Math.Sqrt(a); ++i)
    {
        //i가 소수인 경우
        if (primes[i])
        {
            //i를 제외한 i의 모든 배수 지우기
            int j = 2; //2, 3, 4, ... 
            int compareNum = i * j; //2*2, 2*3, ..., 3*2, 3*3, ...
            
            while (compareNum <= a)
            {
                arr[compareNum] = false;
                j++;
            }
        }
    }
    
    //모든 소수 출력
    for (int i = 2; i <= a; ++i)
    {
        if(primes[i])
        {
            Console.WriteLine(i);
        }
    }

 

예) 1 ~ 100까지 숫자 중 소수를 찾는다

• 1을 제거한다
• 2를 제외한 2의 배수를 제거한다
• 3을 제외한 3의 배수를 제거한다
• 5를 제외한 5의 배수를 제거한다
• 7을 제외한 7의 배수를 제거한다

노가다 방법같지만 아직 소수들 간의 연관성(소수를 생성할 수 있는 공식)이 없으므로

특정 범위 내 모든 소수를 찾아야 하는 경우 위 방법이 빠르다