Introduction

본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다…

기타 알고리즘 : 소수 판별 알고리즘

소수(Prime Number)

  • 소수란 1보다 큰 자연수이지만, 1과 자기자신을 제외한 자연수로 나누어 떨어지지 않는 자연수입니다.
    예를 들어,
    6은 1, 2, 3, 6으로 나누어 떨어지므로 소수가 아닙니다.
    7은 1, 7을 제외하고 어떤 수로도 나누어 떨어지지 않으니 소수입니다.
  • 코딩 테스트에서는 어떠한 자연수가 소수인지 아닌지 판별해야 하는 문제가 자주 출제 됩니다.

소수의 판별 : 기본적인 알고리즘

Python

def is_prime_number(x):
	# 2부터 자기 자신까지 나눠 보는 방식
	for i in range(2, x):
		if x % i == 0:
			return False
		return True

print(is_prime_number(4)
print(is_prime_number(4)

# 실행 결과
False
True

C++

#include <bits/stdc++.h>

using namespace std;

bool isPrimeNumber(int x)
{
	for (int i = 2; i < x; i++)
	{
		if (x % i)
			return false;
	}
	return true;
}

int main(void)
{
	cout << isPrimeNumber(4) << '\n';
	cout << isPrimeNumber(7) << '\n';
}

// 실행 결과
0
1

기본 알고리즘의 성능 분석

  • 2부터 x - 1까지의 모든 자연수에 대해서 연산을 수행합니다. -> 모든 수를 하나씩 확인한다는 점에서 시간복잡도는 𝑂(𝑋)입니다.
  • 소수를 확인해야하는 수가 커지면 커질수록 선형적으로 비례하는 형태로 복잡도가 증가하게 됩니다.
    예를들어, 10억의 숫자를 소수 판별을 위해선 10억의 복잡도가 필요하게 되고, 상당한 시간이 소요되게 됩니다.

약수의 성질?

  • 소수를 구하기 위해 약수를 활용하는데, 이때 약수의 성질을 활용하면 연산횟수를 줄여 성능을 높일 수 있습니다.
  • 모든 약수 가운데 약수를 기준으로 곱셈연산에 대해 대칭을 이룹니다.

    예를 들어
    16의 약수는 1, 2, 4, 8, 16 입니다.
    이때 2 × 8 = 16, 8 × 2 = 16은 대칭입니다.

  • 따라서 우리는 특정한 자연수의 모든 약수를 찾을 때, 가운데 약수(제곱근)까지만 확인하면, 그 뒤에 큰 수들은 확인할 필요가 없습니다.

    ▶︎ 16이라고 한다면, 4까지만 확인하면, 8에 대해선 검증할 필요가 없어집니다.
    ▶︎ 따라서 해야할 검증 연산이 1/2로 줄게 됩니다.

값 1 2 4 8 16
대칭 여부 16과 대칭 8과 대칭 2와 대칭 1과 대칭

소수의 판별 : 개선된 알고리즘

Python

import math
# 사실 제곱근 연산을 파이썬은 기본 지원하므로 사용 안해도 됩니다.

def is_prime_number(x):
	# sqrt메소드는 제곱수를 파악하는 용도
	# 제곱근을 정수 int 로 형변환 및 1을 더해 기준이 되는 중간값을 파악함
	for i in range(2, int(math.sqrt(x) + 1)):
		if x % i == 0:
			return False
	return True

# 메소드 사용 없이 계산 방법 Number ** (1/2)
def is_prime_number_no_math(x):
	for i in range(2, int(x**(1/2))):
		if x % i == 0:
			return False
	return True

print(is_prime_number(4))
print(is_prime_number(7))

# 실행 결과
False
True

C++

#include <bits/stdc++.h>

using namespace std;

bool isPrimeNumber(int x)
{
	for (int i = 2; i < (int) sqrt(x); i++)
	{
		if (x % i == 0)
			return false;
	}
	return true;
}

int main(void)
{
	cout << isPrimeNumber(4) << '\n';
	cout << isPrimeNumber(7) << '\n';
}

// 실행 결과
0
1

개선된 알고리즘 성능 분석

  • 2부터 X의 제곱근(소수점 이하 무시)까지의 모든 자연수에 대한 연산을 수행하므로 시간복잡도는 절반으로 줄게 됩니다.
  • 시간복잡도는 𝑂(𝑋½)

🧑🏻‍💻 알고리즘 박살내기 시리즈🧑🏻‍💻