실습_1. 정수론_소수
Updated:
실습
나머지 값
a mod b는 “a를 b로 나눈 나머지 값”을 구하는 연산입니다.
두 자연수 a, b가 주어질 때 a mod b의 값을 반환하는 함수를 작성해 봅시다.
이렇게 해봅시다!
- 입력
a: 자연수
b: 자연수
- 출력
a를 b로 나눈 나머지
- 실행 결과
>> mod(10, 3)
1
>> mod(6, 2)
0
>> mod(5, 7)
5
a를 b로 나누었을 때의 나머지 값을 반환하는 함수를 작성해보세요.
def mod(a, b):
return a%b
print(mod(10,3))
소수 판별
어떤 수 n이 소수인지 알아보려면 2부터 n-1까지의 수로 n을 나누어서 나머지가 0인 경우가 없음을 보이는 방법이 일반적입니다.
주어진 숫자가 소수임을 확인하는 함수를 작성해 봅시다.
- 입력
n: 자연수
- 출력
소수이면 True, 소수가 아니면 False.
- 실행 결과
>> isPrime(1)
False
>> isPrime(3)
True
>> isPrime(6)
False
- 이렇게 해봅시다!
2부터 n-1까지의 수로 n을 나누어보는 반복문을 작성해보세요.
나누어서 나온 나머지에 따라 소수의 여부를 판별해보세요.
def isPrime(n):
# 1. n이 1인 경우, False를 반환
if n == 1:
return False
# 2. n이 합성수이면, False를 반환
for i in range(2, n):
if n % i == 0:
return False
# 3. n이 소수면, True를 반환
return True
print(isPrime(1))
에라토스테네스의 체
에라토스테네스의 체 알고리즘의 핵심은 어떤 소수를 찾았을때 이 소수의 모든 배수는 소수가 아님을 알기때문에 후보군에서 제외하는 것입니다.
n보다 작은 모든 소수의 리스트를 구하는 함수를 에라토스테네스의 체 알고리즘으로 구현해봅시다.
- 입력
n: 2보다 큰 자연수
- 출력
n보다 작은 모든 소수의 리스트
- 실행 결과
>> eratosthenes(10)
[2, 3, 5, 7]
>> eratosthenes(20)
[2, 3, 5, 7, 11, 13, 17, 19]
>> eratosthenes(30)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
- 이렇게 해봅시다!
주어진 스켈레톤 코드의 To-do를 채워 함수를 완성해보세요.
sieve 리스트에서 i의 배수에 해당하는 위치의 원소를 False로 바꿔보세요.
def eratosthenes(n):
# n개의 True 값이 들어있는 목록을 준비
# (True는 소수, False는 합성수를 의미)
sieve = [True] * n
# To-do - pass는 지우고 코드를 작성해주세요.
# 2부터 n까지 하나씩 순차적으로 소수 여부를 판단
for i in range(2, n):
# 1. i가 소수인 경우 i의 배수를 False로 변경
# 2. i는 소수이므로 True값을 유지
cnt = 1
while True:
cnt+=1
if i*cnt >= n:
break
sieve[i*cnt] = False
# 값이 True인 숫자를 추려낸다
result = []
for i in range(2, n):
if sieve[i] == True :
result.append(i)
return result
print(eratosthenes(10))
소인수
어떤 수 n을 나누는(나누면 나머지가 0이되는) 소수를 n의 소인수라고 부릅니다.
주어진 n에 대해 가장 큰 소인수를 구하는 함수를 작성해 봅시다.
- 입력
n: 2보다 큰 자연수
- 출력
n의 가장 큰 소인수
- 실행 결과
>> greatPrimeFacter(6)
3
>> greatPrimeFacter(7)
7
>> greatPrimeFacter(10)
5
- 이렇게 해봅시다!
n 보다 작거나 같은 소수의 리스트를 구해보세요.
구한 소수 중 n을 나눌 수 있는(나머지가 0이되는) 가장 큰 소수를 찾아보세요.
def greatPrimeFacter(n):
# 1. 소인수의 후보군을 추리기 위해, 우선 n보다 같거나 작은 소수를 모두 구한다.
# n도 소수일 수 있기 때문에 n+1을 사용한다.
# 1-1. n+1개의 True 값이 들어있는 목록을 준비
sieve = [True] * (n+1)
# 1-2. 2부터 n까지 하나씩 순차적으로 소수 여부를 판단
for i in range(2, n+1):
if sieve[i] == True:
for j in range(i+i, (n+1), i):
sieve[j] = False
# 1-3. n보다 같거나 작은 모든 소수 값을 prime_list 에 저장
prime_list = [i for i in range(2,n+1) if sieve[i] == True]
result = -1
for prime in prime_list:
while n % prime == 0:
result = prime
n /=prime
print(result)
# 2. prime_list에서 가장 큰 n의 인수를 구한다.
# To-do - pass는 지우고 코드를 작성해주세요.
return result
print(greatPrimeFacter(6))
소인수분해
소인수분해는 큰 수에서는 매우 오래 걸리는 작업이지만 비교적 작은 수는 비교적 빠른 시간 안에 처리할 수 있습니다.
주어진 수 n을 소인수분해하는 함수를 작성해 봅시다.
- 입력
n: 5000이하의 자연수
- 출력
n의 오름차순 정렬된 소인수 리스트
- 실행 결과
>> primeFactor(10)
[2, 5]
>> primeFactor(100)
[2, 2, 5, 5]
>> primeFactor(210)
[2, 3, 5, 7]
- 이렇게 해봅시다!
n 보다 작은 소수 리스트를 구해보세요.
작은 소수부터 n을 나누어보아서 소인수를 찾아보세요.
찾은 소인수는 따로 저장해두고 n은 다음 소인수를 찾기 위해 적절히 바꿔보세요.
# n 보다 작은 모든 소수의 리스트를 반환
def eratosthenes(n):
sieve = [True] * n
for i in range(2, n):
if sieve[i] == True:
for j in range(i+i, n, i):
sieve[j] = False
return [ i for i in range(2,n) if sieve[i] == True]
def primeFactor(n):
# n과 같거나 작은 모든 소수를 원소로 가지는 리스트 생성
l = eratosthenes(n+1)
print(l)
# l에 담긴 각 소수가 n의 소인수인지 확인해봅니다.
i = 0
result = []
while i < len(l):
# To-do - pass는 지우고 코드를 작성해주세요.
# 1. 만약 현재 소수가 n의 소인수라면, result 리스트에 담고 n을 현재 소수로 나눕니다.
# 2. 현재 소수가 n의 소인수가 아니라면 다음 소수로 넘어갑니다.
if n % l[i] == 0:
result.append(l[i])
n /= l[i]
else:
i+=1
return result
# 결과 출력을 위한 코드입니다. 자유롭게 값을 바꿔보며 확인해보세요.
print(primeFactor(100))
미션
n번째 소수
첫 번째 소수는 2, 두 번째 소수는 3입니다. 그렇다면 50번째 소수는 몇일까요?
n번째의 소수를 구하는 함수를 작성해 봅시다.
- 입력
n: 50000이하의 자연수
- 출력
n번째 소수
- 실행 결과
>> nthPrime(1)
2
>> nthPrime(3)
5
>> nthPrime(5)
11
- 이렇게 해봅시다!
충분한 크기의 소수 리스트를 구해보세요.
리스트의 n번째에 어떤 소수가 있는지 확인하세요.
def nthPrime(n):
# To-do
# 충분히 큰 크기(1000000 정도)를 가진 리스트를 생성하고
# 에라토스테네스의 체를 사용해 n번째의 소수를 찾아 반환하세요.
arr = [0 for i in range(1000001)]
result_arr = []
for i in range(2,len(arr)):
if arr[i] == 0:
result_arr.append(i)
tmp = i
while tmp < len(arr):
arr[tmp] = 1
tmp+=i
return result_arr[n-1]
print(nthPrime(1))
소수의 합
에라토스테네스의 체를 사용하면 주어진 범위의 소수를 빠르게 구할 수 있었습니다.
주어진 n보다 작은 모든 소수의 합을 구하는 함수를 작성해 봅시다.
- 입력
n: 2보다 큰 자연수
- 출력
n보다 작은 모든 소수의 합
- 실행결과
>> primeSum(5)
5
>> primeSum(10)
17
>> primeSum(20)
77
- 이렇게 해봅시다!
n보다 작은 소수의 리스트를 구해서 그 합을 구하는 함수를 작성해보세요.
def primeSum(n):
# 에라토스테네스의 체를 사용해서 n보다 작은 소수의 리스트를 찾고,
# sum()을 사용해 리스트의 합을 반환해보세요.
check = [False for i in range(n)]
Sum = 0
for i in range(2,n):
if not check[i]:
print(i)
Sum+=i
tmp = i
while tmp < n:
check[tmp] = True
tmp+=i
return Sum
print(primeSum(5))
효율적인 소수 판별
어떤 수 n이 소수인지를 알아보기 위해서는 2부터 n-1까지 나눠보아 나머지가 0이 되는지를 확인해보면 됩니다. 이 경우 최대 n-3번의 계산을 하게 됩니다. 하지만 효율적인 방법을 사용하면 이것을 \sqrt{n}/2 (n**1.2)/2까지 줄일 수 있습니다. 다음의 성질을 사용하여 효율적으로 소수를 판별하는 함수를 작성해 봅시다.
2를 제외한 모든 소수는 홀수이다.
(n**1.2)보다 큰 수는 n을 나누지 못한다. (나머지가 0이 될 수 없다.)
- 입력
n: 자연수
- 출력
소수라면 True, 소수가 아니라면 False를 반환.
- 실행 결과
>> isPrime(1)
False
>> isPrime(3)
True
>> isPrime(6)
False
def isPrime2(n):
if n == 1:
return False
di = int(n**(1/2))
print(di)
for i in range(2,di+1):
if n % i == 0:
return False
return True
print(isPrime2(6))
메르센 소수
2^{n}−1 꼴의 형태로 나타나는 수를 메르센 수라고 부르고, 그 중 소수인 수를 메르센 소수라고 부릅니다. 메르센 소수는 매우 큰 소수에서 주로 나타나며 가장 최근에 발견된 메르센 소수는 무려 23,249,425자리에 이릅니다.
n이 주어졌을 때 2^{n}−1이 메르센 소수인지 판별하는 함수를 작성해 봅시다.
- 입력
n: 50이하의 자연수
- 출력
2^{n}−1이 소수라면 True, 아니라면 False
- 실행 결과
>> mersenne(1)
False
>> mersenne(2)
True
>> mersenne(3)
True
- 이렇게 해봅시다!
주어진 n으로 메르센 수 2^{n}−1을 계산해보세요.
계산한 메르센 수가 소수인지 판별해보세요.
def mersenne(n):
# 2^n - 1 이 소수인지 아닌지 판별하는 함수를 작성하고, 이를 반환해봅시다.
if n == 1:
return False
num = 2**n - 1
di = int(num**(1/2))+1
for i in range(2, di):
if num % i == 0:
return False
return True
print(mersenne(1))
Leave a comment