소수 쉽게 구하는 법 - sosu swibge guhaneun beob

소인수분해는 이름 그대로 어떤 자연수를 소인수로 분해하는 거예요. 소인수분해를 이용하면 약수를 구하기도 쉽고, 약수의 개수를 구하기도 아주 쉬워요. 그리고 최대공약수와 최소공배수를 구하기도 쉽고요.

이 글에서는 소인수가 뭔지 어떻게 소인수로 나누는지 알아볼 거예요. 나눗셈을 응용해서 소인수분해를 하는데, 일반적인 나눗셈과 살짝 달라요. 오히려 더 쉬울 수도 있어요.

이 글에서 나오는 수는 모두 자연수예요.

소인수분해

약수와 인수, 소인수

나눗셈은 이렇게 표현할 수 있죠?

(나눠지는 수) ÷ (나누는 수) = (몫) + (나머지)

여기서 나머지가 0일 때 (나누는 수)를 (나눠지는 수)의 약수라고 해요.

12 ÷ 1 = 12,   12 ÷ 12 = 1
12 ÷ 3 = 4,   12 ÷ 4 = 3

12를 1이나 12로 나누면 나머지가 0이잖아요. 그래서 1과 12는 12의 약수인 거예요. 3, 4도 마찬가지고요.

인수는 어떤 수나 식을 곱하기만으로 표현했을 때 곱해지는 각각의 것들을 말해요.

1 × 12 = 12
3 × 4 = 12

1과 12를 곱했더니 12가 됐죠? 다른 거 없이 곱하기만 했잖아요. 이때, 1과 12가 12의 인수예요. 3, 4도 12의 인수고요.

그러니까 약수는 나눗셈을, 인수는 곱셈을 기준으로 한다고 생각하면 쉬워요.

인수 중에서 소수인 것들을 소인수라고 해요. 소수인 인수죠. 12의 인수 중 소수는 2, 3이니까 소인수는 2, 3이에요.

다음 수의 인수 중 소인수를 모두 구하여라.
(1) 10       (2) 25

(1)에서 10의 인수 1, 2, 5, 10에서 소수는 2, 5이므로 소인수는 2, 5

(2) 25의 인수는 1, 5, 25 에서 소수는 5뿐이므로 소인수는 5

소인수분해

소인수분해는 자연수를 소인수들의 곱으로 표현하는 걸 말해요. 그렇다고 해서 12의 소인수는 2, 3이니까 2 × 3 이렇게 쓰면 안 돼요.

소인수분해하는 방법은 몇 가지가 있는데, 가장 많이 사용하고 가장 쉬운 방법 하나만 설명할게요. 자연수를 소수가 나올 때까지 계속 소수로 나누는 거지요.

60을 소인수분해 해볼까요?

60을 가장 작은 소수 2로 나눠요. 몫이 30이 되는데 이걸 또 소수 2로 나누면 15가 되죠? 15는 2로 나누어지지 않아요. 그래서 다음으로 큰 소수인 3으로 나누는 거예요. 15를 3으로 나눴더니 5가 나왔죠? 5는 소수이므로 여기서 끝. 왼쪽에 있는 세 수와 마지막 나온 몫이 모두 소인수예요.

1. 소수 구하기 알고리즘에 대하여

알고리즘을 공부하는 사람이라면 누구나 소수를 찾는 문제에 직면하게 된다.

가장 쉽게는 가능한 모든 수 범위에서 소수를 구할 수 있지만, 범위가 클 경우 시간이 매우 오래 걸린다.

그러므로 큰 범위에서 소수를 찾기 위해서는 효율적인 알고리즘을 사용할 필요가 있는데,

여기에서 알아볼 알고리즘이 '에라토스테네스의 체' 이다.

2. 에라토스테네스의 체

'에라토스테네스(Eratosthenes)의 체'란, 다음과 같이 반복적인 과정을 반복함으로서

주어진 범위에서의 소수를 찾는 것이다.

(1) 2부터 시작해, 2를 제외하고 2의 배수들을 모두 제외시킨다.

(2) 3부터 시작해, 3을 제외하고 3의 배수들을 모두 제외시킨다.

(3) 4는 이미 제외되었으므로, 5부터 시작하고 5를 제외하고 5의 배수들을 모두 제외시킨다.

(4) 6은 이미 제외되었으므로, 7부터 시작하고 7을 제외한 7의 배수들을 모두 제외시킨다.

위의 과정을 지속적으로 반복하면 남아있는 수들이 소수가 된다.

참고로 여기에는 다음과 같은 테크닉을 이용해 계산을 빠르게 할 수 있다.

- N이 소수인지는 판별하려면 루트 N 까지만 나누어서 0으로 나누어 떨어지지 않으면 된다는 사실

- 범위를 증가시킬 때 1씩 증가시키는 것이 아닌, 배수씩 증가시키는 테크닉

3. 구현

#include <iostream>
#include <cmath>
#include <string.h>

using namespace std;

int main(void)
{
	int N;
    cin >> N;
    
    bool *arr = new bool[N+1];
    memset(arr, 1, sizeof(bool) * (N+1));
    
    int root = sqrt(N);
    
    for(int i = 2; i <= root; i++)
    {
    	if(arr[i])
        	for(int j = i + i; j <= N; j += i)
            	arr[j] = false;
    }
    
    for(int i = 2; i <= N; i++)
    	if(arr[i]) cout << i << '\n';

	return 0;
}

728x90

반응형

공유하기

게시글 관리

'Programming > 알고리즘' 카테고리의 다른 글

1과 자기 자신으로만 나누어지는 수인 소수를 구하는 문제는 알고리즘 면접 문제로 보기 제격인 문제입니다. 소수 판별을 하는 방법에는 많은 방법이 있지만, 여기서는 간단하고 쉽게 짤 수 있는 에라토스테네스의 채에 대해 알아보겠습니다.

에라토스테네스의 채의 원리는 간단합니다. 소수를 판별하기 위해 n 이하의 배열을 선언합니다. 그 다음, 배열에 1번도 방문한 적 없다면 그 수를 소수로 출력하고, 그 수의 배수들을 전부 방문 체크 해주면 됩니다. 이를 그림으로 표현하면 다음과 같습니다.

(출처 : 위키백과)

이제 이것을 소스코드로 구현 해보겠습니다. 언어는 C++로 진행하겠습니다.

bool isPrime[1001];
void sieveOfEratosthenes(int n)
{
}

isPrime 배열은 n의 최댓값이 1000이라는 가정하에 1000까지 검사하기 위하여 1001칸을 선언하였습니다. 이제 함수 안의 내용을 작성해 봅시다. 위에 적었던 내용을 그대로 소스코드에 옮겼습니다.

void sieveOfEratosthenes(int n)
{
    for (int i = 2; i <= n; i++)



    {
        /*방문한 적 없다면 소수이다.*/
        if (isPrime[i] == false)
        {
            cout << i << " ";
            /*이 수의 배수는 소수가 아님이 자명하므로 모두 방문처리해준다.*/
            for (int j = i * 2; j <= n; j += i) isPrime[j] = true;
        }
    }
}

그리고 main 함수에 검사를 할 수 있도록 위의 함수를 호출합니다.

int main()
{
    sieveOfEratosthenes(1000);
}

결과를 확인해 보겠습니다.

정상적으로 소수가 출력됨을 알 수 있습니다.

이 알고리즘의 시간 복잡도는 어떻게 될 까요? 어떠한 소수에 대해, n 이하에서 소수의 배수들을 모두 체크해 주므로 for문의 반복 횟수가 $(n/2 + n/3 + n/5 + n/7 + n/11 + ...)$ 로 갑니다. 이를 시간 복잡도로 표현하면 다소 복잡한 $O(n log logn)$ 이 됩니다.