소수(Prime Number)

1과 자기자신 외에는 약수를 갖지 않는 수를 소수라고 한다.
예를 들어, 11의 약수는 1과 11 뿐이기 때문에 소수가 맞다. 반면 6은 1, 2, 3, 6을 약수로 갖기 때문에 소수가 아니다.

소수 판단 방법 1. 약수 이용

그렇다면 소수를 판단할 수 있는 가장 직관적인 방법은 알고자 하는 숫자가 1과 자기 자신 외의 다른 수로 나누어 떨어지는지 확인하면 된다.

코드 (c++)

int main(void)
{
	int n;
	int flag = 0; //flag = 0 : 소수, flag = 1 : 소수 아님
	scanf("%d", &n);
	if (n <= 1) flag = 1; //입력값이 1 이하이면 소수가 아님
	else
	{
		for (int i = 2; i < n; i++) //2부터 자기자신 전까지 
		{
			if (n % i == 0) //나누어 떨어지는지 확인
			{
				flag = 1; //나누어지면 소수가 아니므로
				break; // 더 이상 반복문을 돌릴 필요 없음
			}
		}
	}
	if (flag) printf("소수 X\n");
	else printf("소수 O\n");
}

이렇게 소수를 찾을 때의 단점은 불필요한 연산이 많다는 것이다. 예를 들어 16이라는 숫자의 약수를 생각해보면 1X16, 2X8, 4X4 인데, 숫자 2부터 16의 제곱근인 4까지만 확인해보아도 된다. (대칭을 이루기 때문에)

소수 판단 방법 2. 제곱근 이용

조금 더 효율적인 방식으로 코드를 수정하면 아래와 같다.

• 제곱근을 구하기 위해 #include < math.h> 추가

코드 (c++)

int main(void)
{
	int n;
	int flag = 0;
	scanf("%d", &n);
	if (n <= 1) flag = 1;
	else
	{
		for (int i = 2; i <= sqrt(n); i++) //2부터 숫자의 제곱근까지 반복 범위 좁힘
		{
			if (n % i == 0)
			{
				flag = 1;
				break;
			}
		}
	}
	if (flag) printf("소수 X\n");
	else printf("소수 O\n");
}

소수 판단 방법 3. 에라토스테네스의 체

이 방법은 어떤 수 n이 주어졌을 때, 2부터 주어진 숫자까지의 소수를 구할 때 유용하다. 소수를 찾는 방법 중에 가장 효율성이 좋다.

그림으로 과정 이해하기

N = 37 이라고 하자.

1. 2부터 N까지 모든 자연수를 나열한다.
   
2. 2부터 시작하여 자기 자신 제외하고 2의 배수들은 모두 제거한다.
   
3. 3부터 시작하여 자기 자신 제외하고 3의 배수들은 모두 제거한다.
   
4. 4는 이미 지워졌으니 pass하고 그 다음 수인 5부터 시작하여 5의 배수(10, 15, 20, 25, ...)는 모두 제거한다.
   
5. 이런식으로 반복하게 되면 2부터 n이하의 소수들만 남게 된다.
   

코드 (c++)

int main(void)
{
	int n;
	int idx = 0;
	scanf("%d", &n);
	int* arr = (int*)calloc((n + 1), sizeof(int)); //모두 0으로 초기화
	for (int i = 2; i <= n; i++)
	{
		arr[i] = i; // 2부터 n까지 숫자를 배열에 저장
	}

	for (int i = 2; i <= n; i++)
	{
		for (int j = i + i; j <= n; j = j * i)
		{
			arr[j] = 0; //배수들은 0으로
		}
	}

	for (int i = 0; i < n; i++) //소수 출력
	{
		if (arr[i] != 0) printf("%d ", arr[i]);
	}
}

코드 (python)

n = int(input())
arr = [i for i in range(n+1)]
arr[0] = 0
arr[1] = 0

for i in range(2, n+1):
    for j in range(i+i, n+1, i):
        if arr[j] != 0:
            arr[j] = 0 #삭제
print(arr)

에라토스테네스의 체 관련 문제

백준 2960번 - 에라토스테네스의 체
백준 1644번 - 소수의 연속합