모듈러 연산은 나머지를 구하는 연산이다.
A MOD B 또는 a mod b로 표기하며 예를 들면 10 mod 9의 값은 1이다.
(* 피제수인 A값보다 제수의 값인 B가 더 클 경우에는 피제수인 A가 나머지가 된다. ex)) 2 mod 4의 값은 2이다.)
이를 파이썬 코드로 나타내면 다음과 같다.
print(10 % 9)
print(2 % 4)
출력 값은 각각 1, 2
소수의 정의:
소수는 1 보다 큰 자연수 중 1과 그 수 자신만을 약수(約數)로 가지는 수이다.
*여기서 약수(約數)란? -> 어떤 수를 나누어 떨어지게 하는 수. (ex) 자연수 10의 약수는 1, 2, 5, 10) 예시에서 알 수 있듯이 모든 자연수는 1과 자기 자신을 약수로 가진다.
그럼 다시 소수로 돌아와서 3은 약수로 1과 자기 자신인 3만이 존재하니 소수라고 할 수 있다.
그럼 12는 어떨까 12의 약수는 1, 2, 3, 4, 6, 12로 1과 자기 자신인 12 이외의 약수를 가지고 있으니 소수라고 할 수 없다(참고로 12는 합성수이다).
1은 그럼 소수일까?
위에서 소수를 정의할 때 '1 보다 큰 자연수 중'이라고 정의했기 때문에 1은 소수도 아니고 합성수도 아니다.
(이렇게 생각하니 1은 정말 흥미로운 수)
소수를 구하는 파이썬의 코드는?
def primeNum(x):
# 만약 x가 1이라면 False
if x == 1:
return False
# 2부터 x미만(이하 아님)의 수를 x에 나눴을 때, 나눠 떨어지면 False
for i in range(2, x):
if x % i == 0:
return False
# 그 외의 수는 모두 소수
return True
print(primeNum(42))
print(primeNum(73))
결괏값: False, True
소수를 판별하는 또 다른 방법은 '에라토스테네스의 체(Seive of Eratosthenes)'가 있다.
*에라토스테네스의 체는 주어진 범위 내에서 소수를 찾는 가장 빠른 방법이다.
에라토스테네스의 체로 소수를 판별하는 방법의 순서는 다음과 같다.
1. 찾고자 하는 범위의 자연수를 나열한다.
2. 2부터 시작하여, 2의 배수를 지워나간다.
3. 다음 소수의 배수를 모두 지운다.
def prime_list(n):
sieve = [True] * (n + 1)
for i in range(2, (n+1)):
for j in range(i+i, (n+1), i):
sieve[j] = False
return [i for i in range(2, (n+1)) if sieve[i] == True]
print(prime_list(10))
우선 어려울 수 있으니 하나 씩 풀어서 살펴보자.
sieve = [True] * (n + 1)
함수의 첫 째 줄에 n값의 범위 + 1만큼(인덱스는 0부터 시작하기 때문에) True 값이 들어있는 list를 생성한다.
만약 n의 값이 10이라면
-> [True, True, True, True, True, True, True, True, True, True, True]
라는 값의 리스트가 생성이 된다.
for i in range(2, (n+1)):
for j in range(i+i, (n+1), i):
sieve[j] = False
그 다음, 첫 번째 for문을 2부터 n+1의 값까지 반복하도록 설정한다.
그리고 두 번째 for문에서 i+i부터 n+1까지의 값을 반복하도록 설정하는 데,
주의할 점은 두 번째 for문이 한 번 돌 때마다 1씩 증가하는 것이 아닌 i만큼 증가하도록 만든다.
이렇게 for문으로 선택된 값들은 sieve리스트의 해당 index 값을 False로 변환한다.
2로 예를 들어보자
1. 처음 for문의 i는 2이다.
2. 다음 두 번째 for문으로 실행이 옮겨지고 i+i(2+2), 즉 4의 값이 j의 값이 되고
3. sieve[j], 즉 sieve리스트의 4번째 인덱스(sieve [4])의 값은 False로 바뀐다.
4. 아직 두 번째의 범위(n = 10 + 1)가 끝나지 않았기 때문에
5. 다시 두 번째 for문에서 j의 값을 1 증가가 아니라 i(현재 i의 값 = 2) 만큼 증가시켜 j는 6이 된다.
6. 그리고 sieve[6]의 값은 False로 바뀐다.
그리고 이 과정을 j가 n보다 커지거나 같을 때까지 진행한다.
return [i for i in range(2, n) if sieve[i] == True]
마지막은 comprehension 방법으로 sieve[i]의 값이 True인 것만 리스트에 추가해주고 함수에서 리턴을 끝으로 종료한다.
def prime_list(n):
sieve = [True] * (n + 1)
for i in range(2, (n+1)):
for j in range(i+i, (n+1), i):
sieve[j] = False
return [i for i in range(2, (n+1)) if sieve[i] == True]
print(prime_list(10))
그럼 이 함수의 최종 출력문은
-> [2, 3, 5, 7] 이 된다.