나머지 연산 (Modulo Operation)
•
나머지 연산(Modulo Operation)은 나눗셈의 나머지를 구하는 연산을 의미한다.
•
나머지 연산을 표현할 때는 mod로 표현하고, 프로그래밍 언어에서는 보통 %에 해당한다.
python
•
약수 (Divisor)
•
어떤 수 의 약수는 을 나누어 떨어지게 하는 수를 의미한다.
◦
예를 들어, 12의 약수는 1, 2, 3, 4, 6, 12가 존재한다.
•
n의 약수를 구하는 법
◦
시간 복잡도:
◦
1부터 n까지의 모든 수를 살펴보며 나누어떨어지는지 확인하면 구할 수 있다.
python
•
더 효율적으로 n의 약수를 구하는 법
◦
시간 복잡도:
◦
1부터 까지의 모든 수를 살펴보며 나누어떨어지는지 확인하면 구할 수 있다.
◦
까지만 살펴봐도 되는 이유는 에서 이기 때문이다.
python
소수 (Prime Number)
•
소수란 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다.
•
즉, 어떤 수의 약수의 개수가 2개라면 그 수는 소수라고 할 수 있다.
•
따라서, 어떤 수 이 소수인지를 판단하고 싶다면 약수를 구하면 된다.
•
이 소수인지 아닌지 판단하는 법
◦
시간 복잡도:
◦
의 약수를 구하는 과정은 1부터 까지 살펴보면 된다.
◦
의 약수를 구한 후에 개수가 2개인지(1과 자기 자신뿐인지) 확인하면 된다.
python
소인수분해 알고리즘
•
소인수분해는 어떤 수 을 소수(prime number)의 곱으로만 나타내는 것을 의미한다.
•
시간 복잡도:
•
어떤 수 n을 소인수분해하는 방법은 2부터 n까지 살펴 보면서 소수로 나누어보면 된다.
python
에라토스테네스의 체 알고리즘
•
에라토스테네스의 체 알고리즘을 이용하면 이하의 자연수를 소수인지 빠르게 판별할 수 있다.
•
◦
자연수 에 대해 다음과 같은 과정을 반복한다. ()
▪
를 제외한 의 배수를 소수에서 제외시킨다.
▪
에 1을 더한다.
◦
시간 복잡도:
python