소수란 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수이다
6은 1, 2, 3, 6으로 나누어떨어지므로 소수가 아니다
7은 1과 7을 제외하고는 나누어떨어지지 않으므로 소수이다
코딩 테스트에서는 어떠한 자연수가 소수인지 아닌지 판별해야 하는 문제가 자주 출제된다
소수의 판별: 기본적인 알고리즘 (Python)
# 소수 판별 함수(2이상의 자연수에 대하여)
def is_prime_number(x):
# 2부터 (x - 1)까지의 모든 수를 확인하며
for i in range(2, x):
# x가 해당 수로 나누어떨어진다면
if x % i == 0:
return False # 소수가 아님
return True # 소수임
print(is_prime_number(4)) # 4는 소수가 아님
print(is_prime_number(7)) # 7은 소수임
실행 결과
False
True
소수의 판별: 기본적인 알고리즘 (Java)
import java.util.*;
class Main {
// 소수 판별 함수(2이상의 자연수에 대하여)
public static boolean isPrimeNumber(int x) {
// 2부터 (x - 1)까지의 모든 수를 확인하며
for (int i = 2; i < x; i++) {
// x가 해당 수로 나누어떨어진다면
if (x % i == 0) {
return false; // 소수가 아님
}
}
return true; // 소수임
}
public static void main(String[] args) {
System.out.println(isPrimeNumber(4));
System.out.println(isPrimeNumber(7));
}
}
실행 결과
False
True
소수의 판별: 기본적인 알고리즘 성능 분석
2부터 𝑋-1까지의 모든 자연수에 대하여 연산을 수행해야 한다
모든 수를 하나씩 확인한다는 점에서 시간 복잡도는 O(X) 이다
약수의 성질
모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이루는 것을 알 수 있다
예를 들어 16의 약수는 1, 2, 4, 8, 16이다
이때 2 X 8 = 16은 8 X 2 = 16과 대칭이다
따라서 우리는 특정한 자연수의 모든 약수를 찾을 때 가운데 약수(제곱근)까지만 확인하면 된다
예를 들어 16이 2로 나누어떨어진다는 것은 8로도 나누어떨어진다는 것을 의미한다
소수의 판별: 개선된 알고리즘 (Python)
import math
# 소수 판별 함수
def is_prime_number(x):
# 2부터 x의 제곱근까지의 모든 수를 확인하며
for i in range(2, int(math.sqrt(x)) + 1):
# x가 해당 수로 나누어떨어진다면
if x % i == 0:
return False # 소수가 아님
return True # 소수임
print(is_prime_number(4)) # 4는 소수가 아님
print(is_prime_number(7)) # 7은 소수임
실행 결과
False
True
소수의 판별: 개선된 알고리즘 (Java)
import java.util.*;
class Main {
// 소수 판별 함수(2이상의 자연수에 대하여)
public static boolean isPrimeNumber(int x) {
// 2부터 x의 제곱근까지의 모든 수를 확인하며
for (int i = 2; i <= Math.sqrt(x); i++) {
// x가 해당 수로 나누어떨어진다면
if (x % i == 0) {
return false; // 소수가 아님
}
}
return true; // 소수임
}
public static void main(String[] args) {
System.out.println(isPrimeNumber(4));
System.out.println(isPrimeNumber(7));
}
}
댓글