📝스터디노트 9일차 범위
기초 수학 3~6(소인수 분해, 최대 공약수)
📖 소인수 분해
‣ 소수는 어떠한 수가 약수를 1과 자기자신만을 가지고 있는 수가 소수(소인수)이다.
‣ 어떠한 수를 소인수의 곱으로만 나타내는 것이다.
inputNumber = int(input('1보다 큰 정수 입력: '))
n = 2
while n <= inputNumber: # n이 입력값보다 작을 동안 돈다.
if inputNumber % n == 0: # 나머지가 0 이면 약수
print('소인수: {}'.format(n))
inputNumber /= n # 안될떄까지 계속 나누어준다.
else:
n += 1
1. 1은 소수가 아니기에 2로 초기화하고 2부터 시작한다.
2. n으로 입력값을 나눴을 떄 0이면 약수이다.
3. 나누고 남은 수를 inputNumber에 다시 넣어주어 입력값보다 n이 커질때까지 반복한다.(탈출조건)
4. n으로 나누어서 나머지가 0이 아니라면 n값을 증가해서 계속 반복한다.
소인수 분해의 가장 기본이 되는 예제였고, 다음 예제를 본다.
# 입력값에 x를 곱하면 y의 제곱일때 x의 가장 작은값
inputNumber = int(input('1보다 큰 정수 입력: '))
searchNumber = [] # 약수를 담는 리스트
n = 2
while n <= inputNumber: # n이 입력값보다 작을 동안 돈다.
if inputNumber % n == 0: # 나머지가 0 이면 약수
print('소인수: {}'.format(n))
if searchNumber.count(n) == 0: # 소수가 리스트에 없을떄 담아준다.
searchNumber.append(n) #append 는 리스트에 추가해주는 함수
elif searchNumber.count(n) == 1: # 소수가 리스트에 1개라도 있으면,
searchNumber.remove(n) # remove 함수로 리스트에서 지운다.
inputNumber /= n # 안될떄까지 계속 나누어준다.
else:
n += 1
print('searchNumber: {}'.format(searchNumber))이 예제는 입력값에 어떤한 수 x를 곱했을 때 y의 제곱이 된다면 x의 가장 작은 값을 구한다.
1. 위와 비슷하나 약수를 담을 searchNumber 라는 리스트를 만들어준다.
2. 약수를 구하는 지점에서 append 함수를 통해 리스트에 소수를 추가한다.
3. 만약 count를 했을 때 이미 리스트에 해당 소수가 있다면 remove 함수를 통해 제거한다.
소수의 제곱형태로 나타내어 예를 들어 72라는 입력값이라면 2x2x2 x 3x3 인데, 2만 더 곱해진다면
(2x2x3)^2 으로 나눌 수 있기 때문에 72 라는 입력값을 최소값 x는 2이다.
📖 공약수, 최대 공약수 구하기.
‣ 공약수는 2개 이상의 수를 나누었을 떄 나머지가 0이되는 공통된 약수를 말한다.
‣ 최대 공약수는 그 공약수들 중 가장 큰 수 를 말한다.
# 두 수의 공약수, 최대공약수 구하기.
num1 = int(input('1보다 큰 정수 입력: ')) #두 수의 공약수, 최대 공약수이기 때문에
num2 = int(input('1보다 큰 정수 입력: ')) #입력값이 2개가 필요하다.
maxNum = 0 #최대 공약수를 담을 maxNum 초기화
for i in range(1, (num1 + 1)): # 1부터 num1 수까지 반복 / num1 을 넘어가면 공약수의 의미가 없기때문에
if num1 % i == 0 and num2 % i == 0: #두 수를 나눴을때 나머지가 0인 수는 공약수
print('공약수: {}'.format(i))
maxNum = i #공약수가 나올때마다 담다가 마지막 수만 출력될 것.
print('최대공약수: {}'.format(maxNum))
1. 두 수를 입력값으로 받고, 최대 공약수를 담을 maxNum을 초기화해준다.
2. 공약수가 대상이 되는 수들 중 가장 작은 수보다 크면 의미가 없기 떄문에 num1 < num2 라는 가정하에 num1까지만 for문으로 반복한다.
3. 두 수를 나눴을 떄 나머지가 0임을 만족하는 수를 maxNum에 담아주고 다음 수로 넘어가서 반복한다.
지금은 기본인 두 수로 보았는데, 세 개 네 개가 되면 방식만 살짝 바꿔주고 똑같이 반복하면된다.
# 세 수의 공약수, 최대공약수 구하기.
num1 = int(input('1보다 큰 정수 입력: ')) #세 수의 공약수, 최대 공약수이기 때문에
num2 = int(input('1보다 큰 정수 입력: ')) #입력값이 3개가 필요하다.
num3 = int(input('1보다 큰 정수 입력: ')) #입력값이 3개가 필요하다.
maxNum = 0 #최대 공약수를 담을 maxNum 초기화
for i in range(1, (num1 + 1)): # 1부터 num1 수까지 반복 / num1 을 넘어가면 공약수의 의미가 없기때문에
if num1 % i == 0 and num2 % i == 0 and num3 % i == 0: #세 수를 나눴을때 나머지가 0인 수는 공약수
print('공약수: {}'.format(i))
maxNum = i #공약수가 나올때마다 담다가 마지막 수만 출력될 것.
print('최대공약수: {}'.format(maxNum))
1. 세 개의 수를 비교해야 하기 때문에 입력을 세 개로 바꾸어 주었다.
2. 나머지가 0인 수를 구할 때도 세 개의 수를 and 로 묶어서 비교한다.
3. 똑같이 그 수를 maxNum에 담아서 최대 공약수를 출력한다.
공약수, 최대 공약수를 이렇게 구할 수 도 있지만, <테라토스테네스의 체>처럼 <유클리드 호제법>이라는 방식으로 구할 수 있다.
첫 자리부터 num1, num2, r 이라 했을 떄, num1을 num2로 나눈 값을 r에 적고 시작한다.
만약 num1보다 num2가 크다면 첫 나머지 값은 그대로 num1이 될 것이다.
그렇게 num1 % num2 = r 형식으로 쓰여있다면 다음 줄엔
num1 자리에 num2가 오고 num2 자리에 r값이 와서 r을 계산해가며 내려간다.
그리고 나머지 값이 0이 될 때 까지 진행하고 그 때 num2 자리의 값이 최대 공약수가 되는 것이다.
# 유클리드 호제법
num1 = int(input('1보다 큰 정수 입력: '))
num2 = int(input('1보다 큰 정수 입력: '))
temp1 = num1; temp2 = num2
while temp2 > 0:
temp = temp2
temp2 = temp1 % temp2
temp1 = temp
print('{}, {}의 최대공약쉬 {}'.format(num1, num2, temp1))
for n in range(1, (temp + 1)):
if temp1 % n == 0:
print('{}, {}의 공약수: {}'.format(num1, num2, n))
1. 앞서 설명한 것처럼 num1, num2를 받고,
2. temp2 가 0 이 될 때 까지 반복을 해준다.
3. temp 에 잠시 temp2를 넣어두고 자리를 옮긴 후 temp1 에 temp2를 넣어주는 식으로 반복한다.
🔥🔥바쁜시간 쪼개서 매일매일 성장해 나가는 모습을 기록하자🔥🔥
