01. 약수와 소수
- 약수
어떤 수를 나누어 떨어지게 하는 수. 나머지가 0
- 2
2 / 1 = 2
2 / 2 = 1 - 3
3 / 3 = 3
3 / 3 = 1 - 8
8 / 1 = 8
8 / 2 = 4
8 / 4 = 2
8 / 8 = 1 - 9
9 / 1 = 9
9 / 3 = 3
9 / 9 = 1 - 15
15 / 1 = 15
15 / 3 = 5
15 / 5 = 3
15 / 15 = 1 - 22
22 / 1 = 22
22 / 2 = 11
22 / 11 = 2
22 / 22 = 1
...
- 소수
약수 중에서, 1과 자신만을 약수로 가지는 수(단, 1은 제외)
- 2
2 / 1 = 2
2 / 2 = 1 - 3
3 / 1 = 3
3 / 3 = 1 - 5
5 / 1 = 5
5 / 5 = 1 - 7
7 / 1 = 7
7 / 7 = 1 - 11
11 / 1 = 11
11 / 11 = 1 - 13
13 / 1 = 13
13 / 13 = 1 - 17
17 / 1 = 17
17 / 17 = 1
...
실습) 1부터 30까지의 숫자 중 5로 나눈 몫과 나머지가 모두 소수인 숫자를 찾아보자
- 몫으로 나올 수 있는 소수를 찾는다
O : 2, 3, 5
X : 6, 10, 15 - (5 * 몫)에 5보다 작은 소수를 더한다
-> 10 / 15 / 25 + 2, 3
-> 12, 13 / 17, 18 / 27, 28
= 12, 13, 17, 18, 27, 28
실습) 1부터 30까지의 숫자 중 소수를 찾아보자
- 2를 제외한 2의 배수 제거
- 3를 제외한 3의 배수 제거
- 5를 제외한 5의 배수 제거
- 7를 제외한 7의 배수 제거
- 11를 제외한 11의 배수 제거
...
002. 약수와 소수(파이썬)
- 파이썬을 이용해서 사용자가 입력한 숫자의 약수를 출력해보자
= 나머지가 0인 숫자 찾기
inputNumber = int(input('0보다 큰 정수 입력: '))
for number in range(1, inputNumber + 1):
if inputNumber % number == 0 :
print('{}의 약수: {}'.format(inputNumber, number))- 파이썬을 이용해서 사용자가 입력한 숫자까지의 소수를 출력하자
inputNumber = int(input('0보다 큰 정수 입력: '))
for number in range(2, inputNumber + 1): #소수니까 2부터 시작
flag = True
for n in range(2, number):
if number % n == 0: #나머지가 0이면 소수의 대상이 아님.
flag = False
break
if flag:
print('{} : 소수'.format(number))
else:
print('{} : \t 합성수'.format(number))
-->
2 : 소수
3 : 소수
4 : 합성수
5 : 소수
6 : 합성수
7 : 소수
8 : 합성수
9 : 합성수
10 : 합성수003. 소인수분해
- 소인수
- 약수(인수) 중에서 소수인 숫자를 소인수라고 한다.
20의 약수(인수): 1, 2(소수), 4, 5(소수), 10, 20
소인수: 2, 5
12의 소인수: 1, 2, 3, 4, 6, 12 -> 2, 3
25의 소인수: 1, 5, 25 -> 5
36의 소인수: 1, 2, 3, 4, 9, 12, 18, 36 -> 2, 3
41의 소인수: 1, 41 -> 41
- 소인수분해
- 1보다 큰 정수를 소인수의 곱으로 나타낸 것
20의 소인수분해 = 2 10 = 2 2 5
12의 소인수분해 = 2 2 3
36의 소인수분해 = 2^2 3^2
25의 소인수분해 = 5^2
41의 소인수분해 = 41
- 소인수분해와 약수
- 소인수분해를 이용해서 약수를 쉽게 찾아낼 수 있다.
실습) 다음의 수를 소인수분해를 통해 약수를 구해보자
14: 1, 2, 7, 14
154: 1, 2, 7, 11, 14, 22, 77, 154
004. 소인수분해(파이썬)
- 소인수분해
- 파이썬을 이용해서 사용자가 입력한 수를 소인수분해하자.
inputNumber = int(input('1보다 큰 정수 입력: '))
n = 2
while n <= inputNumber: #12 / 2 -> # 6 / 2 -> 3
if inputNumber % n == 0:
print('소인수: {}'.format(n))
inputNumber /= n
else:
n += 1
-->
1보다 큰 정수 입력: 1524865
소인수: 5
소인수: 163
소인수: 1871- 72에 x를 곱하면 y의 제곱이 된다고 할 때, x에 해당하는 가장 작은 정수를 구하자
inputNumber = int(input('1보다 큰 정수 입력: '))
n = 2
searchNumbers = [] #자료구조, 리스트활용. 데이터를 여러개 저장함. 소인수들의 개수 세기위함.
while n <= inputNumber: #12 / 2 -> # 6 / 2 -> 3
if inputNumber % n == 0:
print('소인수: {}'.format(n))
if searchNumbers.count(n) == 0:
searchNumbers.append(n)
elif searchNumbers.count(n) == 1:
searchNumbers.remove(n) #기존에 하나가 있다면, 없앰. 짝수가 되면 없앰.
inputNumber /= n
else:
n += 1
print('searchNumbers: {}'.format(searchNumbers))
-->
1보다 큰 정수 입력: 72
소인수: 2
소인수: 2
소인수: 2
소인수: 3
소인수: 3
searchNumbers: [2]= searchNumbers = 더해야 할 가장 작은 정수
005. 최대공약
- 공약수
- 두개 이상의 수에서 공통된 약수를 공약수라고 한다.
12의 약수: 1, 2, 3, 4, 6, 12
20의 약수: 1, 2, 4, 5, 10, 20
공약수: 1, 2, 4
36, 60의 공약수: 2, 3, 4, 6, 12
- 최대공약수
- 공약수 중 가장 큰 공약수라고 한다
12, 20의 최대공약수: 4
- 소인수분해를 이용하면 최대공약수 및 공약수를 구할 수 있다.
거듭제곱 중 밑이 같은 숫자를 찾거나, 지수가 낮은 걸 고름
36, 60의 최대공약수: 2^2 x 3^2 / 2^2 x 3 x 5
= 2^2(밑이 같은) x 3(지수가 낮은) = 12
공약수: 12의 약수
- 좀 더 편리하게 최대공약수 구하는 방법! 소수로 나눗셈 하자!
2 | 12, 20
---------
2 | 6, 10
---------
3 , 5
↓
2 * 2 = 4 = 최대공약수
공약수: 1, 2, 4실습) 다음 수의 최대공약수 및 공약수를 구해보자
- 12, 54, 72의 최대공약수 및 공약수
2 | 12, 54, 72
---------
3 | 6, 27, 36
----------
2 , 9, 12
↓
최대공약수: 6
공약수: 1, 2, 3, 6- 25, 115, 255의 최대공약수 및 공약수
5 | 25, 115, 255
---------
5, 23, 51
↓
최대공약수: 5
공약수: 1, 5실습) 빵 112개와 우유 80개를 학생들에게 남김없이 동일하게 나눠주려고 할 때, 최대 몇 명의 학생이 빵과 우유를 받을 수 있는지 계산해보자. 그리고 학생 한명이 받게 되는 빵과 우유의 개수를 계산해보자
- 112와 80의 최대공약수
2 | 112, 80
---------
2 | 56, 40
----------
2 | 28, 20
----------
2 | 14, 10
----------
7, 5
↓
- 최대공약수: 16
- 학생 한 명이 받게 되는 빵과 우유 개수: 빵 7개, 우유 5개006. 최대공약수(파이썬)
- 두 개의 수를 입력하면 공약수와 최대공약수를 출력하는 코드를 작성하자
num1 = int(input('1보다 큰 정수 입력: '))
num2 = int(input('1보다 큰 정수 입력: '))
for i in range(1, (num1 + 1)): #공약수니까 더 작은 num1을 기준으로
if num1 % i == 0 and num2 % i == 0: #공통된 약수
print('공약수: {}'.format(i))
maxNum = i
print('최대공약수: {}'.format(maxNum))
-->
1보다 큰 정수 입력: 12
1보다 큰 정수 입력: 36
공약수: 1
공약수: 2
공약수: 3
공약수: 4
공약수: 6
공약수: 12
최대공약수: 12- 세개의 수를 입력하면 공약수와 최대공약수를 출력하는 코드를 작성하자
num1 = int(input('1보다 큰 정수 입력: '))
num2 = int(input('1보다 큰 정수 입력: '))
num3 = int(input('1보다 큰 정수 입력: '))
for i in range(1, (num1 + 1)): #공약수니까 더 작은 num1을 기준으로
if num1 % i == 0 and num2 % i == 0 and num3 % i == 0: #공통된 약수
print('공약수: {}'.format(i))
maxNum = i
print('최대공약수: {}'.format(maxNum))
-->
1보다 큰 정수 입력: 72
공약수: 1
공약수: 2
공약수: 3
공약수: 6
최대공약수: 6- 유클리드 호제법
- x, y의 최대공약수는 y, r(x%y)의 최대공약수와 같다.
x y r
12 % 36 = 12
↙ ↙ ↲
36 % 12 = 3 나머지가 0일 때까지 나눗셈한다.
↙ ↙ ↲
12 % 3 = 0
: 최대공약수- 유클리드 호제법을 이용해서 최대공약수를 구할 수 있다.
x = temp1
y = temp2 = 최대공약수
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, (temp1 + 1)):
if temp1 % n == 0:
print('{}, {}의 공약수: {}'.format(num1, num2, n))
-->
1보다 큰 정수 입력: 12
1보다 큰 정수 입력: 36
12, 36의 최대공약수: 12
12, 36의 공약수: 1
12, 36의 공약수: 2
12, 36의 공약수: 3
12, 36의 공약수: 4
12, 36의 공약수: 6
12, 36의 공약수: 12007. 최소공배수
- 공배수
- 두개 이상의 수에서 공통된 배수를 공배수라고 한다
3의 배수: 3, 6, 9, 12, 15, ..., 30
5의 배수: 5, 10, 15, ... , 30
공배수: 15, 30, ...
3, 4의 공배수: 12, 24, ...
2, 3, 4의 공배수: 24, 48, ...
- 최소공배수
- 공배수 중 가장 작은 수를 최소공배수라고 한다
3, 5의 공배수: 15, 30, ...
최소공배수: 15
- 소인수분해를 이용하면 최소공배수 및 공배수를 구할 수 있다.
최소공배수 = 공통인 소인수의 거듭제곱에서 지수가 크고, 공통 아닌 수를 모두 곱한다.
-
4의 소인수분해(소인수의 곱으로 표현): 2^2
-
12의 소인수분해: 2^2 * 3
-
최소공배수: 2^2 * 3 = 12
-
4와 12의 공배수: 12의 배수
-
6, 12, 15의 최소공배수: 23, 2^2 3, 35 = 2^2 3 * 5 = 60
-
5, 7의 최소공배수: 5*7 = 35
- 좀 더 편리하게 최소공배수 구하는 방법! 소수로 나눗셈하자!
- 6과 12의 최소공배수
2 | 6, 12
---------
3 | 3, 6
----------
1, 2
↓
- 최소공배수: 2 * 3 * 1 * 2 = 12
- 공배수: 12, 24, 36, ...- 6, 12, 15의 최소공배수
2 | 6, 12, 15
------------
3 | 3, 6, 15
------------
1, 2, 5
↓
- 최소공배수: 2 * 3 * 1 * 2 * 5 = 60
- 공배수: 60, 120, ...실습) 다음수의 최소공배수 및 공배수를 구해보자
- 12, 21, 33의 최소공배수 및 공약수
3 | 12, 21, 33
---------
4, 7, 11
↓
- 최소공배수: 3 * 4 * 7 * 11 = 924
- 공배수: 924, 1848, ...- 12, 36, 48의 최소공배수 및 공약수
12 | 12, 36, 48
---------
1, 3, 4
↓
- 최소공배수: 12 * 3 * 4 = 144
- 공배수: 144, 288, ...실습) 2, 5, 8중 하나만 제외하고 나머지 두개의 수는 5를 곱해도 최소공배수에 변함이 없다. 5를 곱했을 때 최소공배수에 변함이 있는 수를 찾아보자.
- 2, 5, 8의 최소공배수 = 40
2 | 2, 5, 8
---------
1, 5, 4
↓
- 최소공배수: 2 * 1 * 5 * 4 = 40- 10(2*5), 5, 8의 최소공배수 = 40
2 | 10, 5, 8
---------
5 | 5, 5, 4
---------
1, 1, 4
↓
- 최소공배수: 2 * 5 * 1 * 1 * 4 = 40- 2, 25(5*5), 8의 최소공배수 = 40 <- 변함있는 수 = 5
2 | 2, 25, 8
---------
| 1, 25, 4
↓
- 최소공배수: 2 * 1 * 25 * 4 = 200- 2, 5, 40(8*5)의 최소공배수 = 40
2 | 2, 25, 40
---------
5 | 1, 25, 20
----------
1, 5, 4
↓
- 최소공배수: 2 * 5 * 5 * 4 = 40008. 최소공배수(파이썬)
- 두개의 수를 입력하면 최소공배수를 출력하는 코드를 작성하자
먼저 최대공약수를 구하고
두 개의 수를 최대공약수로 나눈 몫 = 최소공배수
num1 = int(input('1보다 큰 정수 입력: '))
num2 = int(input('1보다 큰 정수 입력: '))
maxNum = 0
for i in range(1, (num1 + 1)):
if num1 % i == 0 and num2 % i == 0:
print('공약수: {}'.format(i))
maxNum = i
print('최대공약수: {}'.format(maxNum))
minNum = (num1 * num2) // maxNum
print('최소공배수: {}'.format(minNum))
-->
1보다 큰 정수 입력: 10
1보다 큰 정수 입력: 12
공약수: 1
공약수: 2
최대공약수: 2
최소공배수: 60- 세개의 수를 입력하면 최소공배수를 출력하는 코드를 작성하자
두개의 수에 대한 최소공배수를 구한 후, 다시 세번째 수의 공배수를 구한다
num1 = int(input('1보다 큰 정수 입력: '))
num2 = int(input('1보다 큰 정수 입력: '))
num3 = int(input('1보다 큰 정수 입력: '))
maxNum = 0
for i in range(1, (num1 + 1)):
if num1 % i == 0 and num2 % i == 0:
maxNum = i
print('최대공약수: {}'.format(maxNum))
minNum = (num1 * num2) // maxNum
print('{}, {}의 최소공배수: {}'.format(num1, num2, minNum))
newNum = minNum
for i in range(1, (newNum + 1)):
if newNum % i == 0 and num3 % i == 0:
maxNum = i
print('최대공약수: {}'.format(maxNum))
minNum = (newNum * num3) // maxNum
print('{}, {}, {}의 최소공배수: {}'.format(num1, num2, num3, minNum))
-->
1보다 큰 정수 입력: 6
1보다 큰 정수 입력: 12
1보다 큰 정수 입력: 18
최대공약수: 6
6, 12의 최소공배수: 12
최대공약수: 6
6, 12, 18의 최소공배수: 36- 섬마을에 과일, 생선, 야채를 판매하는 배가 다음 주기로 입항한다고 할 때, 모든 배가 입항하는 날짜를 계산해보자
과일선박: 3일 주기 / 생선선박: 4일 주기 / 야채선박: 5일 주기
ship1 = 3; ship2 = 4; ship3 = 5
maxDay = 0
for i in range(1, (ship1 + 1)):
if ship1 % i == 0 and ship2 % i ==0: #공약수
maxDay = i
print('최대공약수: {}'.format(maxDay))
minDay = (ship1 * ship2) // maxDay
print('{}, {}의 최소공배수: {}'.format(ship1,ship2, minDay))
newDay = minDay
for i in range(1, (newDay + 1)):
if newDay % i == 0 and ship3 % i ==0: #공약수
maxDay = i
print('최대공약수: {}'.format(maxDay))
minDay = (newDay * ship3) // maxDay
print('{}, {}, {}의 최소공배수: {}'.format(ship1, ship2, ship3, minDay))
-->
최대공약수: 1
3, 4의 최소공배수: 12
최대공약수: 1
3, 4, 5의 최소공배수: 60009. 진법
- 진법이란?
- 진법이란, 특정 숫자 몇개를 사용해 수를 표시하는 방법이다
- 2진법: 0, 1
- 8진법: 0 ~ 7
- 10진법: 0 ~ 9
- 16진법: 0 ~ 9 , A, B, C, D, E, F(소문자도 ㄱㅊ)
- 10진수를 X진수로 변환
- 10진수 -> 2진수 (2로 나눔)
- 10진수 8
2 | 8
----
2 | 4 -> 0
-----
2 | 2 -> 0
-----
1 -> 0
= 2진수: 1000- 10진수 17
2 | 17
----
2 | 8 -> 1
-----
2 | 4 -> 0
-----
2 | 2 -> 0
-----
1 -> 0
= 2진수: 10001- 10진수 -> 8진수 (8로 나눔)
- 10진수 8
8 | 8
----
1 -> 0
= 8진수: 10- 10진수 17
8 | 17
----
2 -> 1
= 8진수: 21- 10진수 -> 16진수 (16로 나눔)
- 10진수 8
16 | 8
----
0 -> 8
= 8진수: 8- 10진수 17
16 | 17
----
1 -> 1
= 8진수: 11- X진수 -> 10진수
- 2진수 -> 10진수
- 2진수 1000
1 0 0 0
1*2^3 / 0*2^2 / 0 * 2^1 / 0* 2^0(=1)
= 10진수: 8- 2진수 10001
1 0 0 0 1
1*2^4 / 0*2^3 / 0 * 2^2 / 0 * 2^1 / 1* 2^0(=1)
= 10진수: 17- 8진수 -> 10진수
- 8진수 10
1 0
1 * 8^1 / 0* 8^0(=1)
= 10진수: 8- 8진수 21
2 1
2 * 8^1 / 1* 8^0(=1)
= 10진수: 17- 2진수를 8진수로 변환
- 2진수 -> 8진수
뒤에서부터 3자리씩 구분하고, 빈자리는 0으로 채운다
- 2진수 1010100
001 | 010 | 100
0 0 1
0*2^2 / 0 * 2^1 / 1* 2^0(=1) = 1
0 1 0
0*2^2 / 1 * 2^1 / 0* 2^0(=1) = 2
1 0 0
1*2^2 / 0* 2^1 / 0* 2^0(=1) = 4
= 8진수: 124- 2진수 -> 16진수
뒤에서부터 4자리씩 구분하고, 빈자리는 0으로 채운다
- 2진수 1010100
0101 | 0100
0 1 0 1
0*2^3 / 1*2^2 / 0 * 2^1 / 1* 2^0(=1) = 5
0 1 0 0
0*2^3 / 1*2^2 / 0 * 2^1 / 0* 2^0(=1) = 4
= 8진수: 54010. 진법(파이썬)
- 10진수를 X진수로 변환
- 10진수 -> 2진수, 8진수, 16진수
binary : bin( ) -> 0b1110
octal : oct( ) -> 0o36
Hexadecimal : hex( ) -> 0x1e
= 변환결과는 문자열
dNum = 30
print('2진수: {}'.format(bin(dNum)))
print('8진수: {}'.format(oct(dNum)))
print('16진수: {}'.format(hex(dNum)))
print('2진수: {}'.format(type(bin(dNum))))
print('8진수: {}'.format(type(oct(dNum))))
print('16진수: {}'.format(type(hex(dNum))))
print('2진수: {}'.format(format(dNum, '#b')))
print('8진수: {}'.format(format(dNum, '#o')))
print('16진수: {}'.format(format(dNum, '#x')))
print('2진수: {}'.format(format(dNum, 'b')))
print('8진수: {}'.format(format(dNum, 'o'))) #타입은 여전히 str
print('16진수: {}'.format(format(dNum, 'x')))
print('{0:#b}, {0:#0}, {0:#x}'.format(dNum))- X진수를 10진수로 변환
- X진수 -> 10진수
dNum = 30
print('2진수(0b11110) -> 10진수: {}'.format(int('0b11110', 2)))
print('8진수(0o36) -> 10진수: {}'.format(int('0o36', 8)))
print('16진수(0x1e) -> 10진수: {}'.format(int('0x1e', 16)))- X진수 -> X진수
dNum = 30
print('2진수(0b11110) -> 8진수: {}'.format(oct(0b11110)))
print('2진수(0b11110) -> 10진수: {}'.format(int(0b11110)))
print('2진수(0b11110) -> 16진수: {}'.format(hex(0b11110)))
print('8진수(0o36) -> 2진수: {}'.format(bin(0o36)))
print('8진수(0o36) -> 10진수: {}'.format(int(0o36)))
print('8진수(0o36) -> 16진수: {}'.format(hex(0o36)))
print('16진수(0x1e) -> 2진수: {}'.format(bin(0x1e)))
print('16진수(0x1e) -> 8진수: {}'.format(oct(0x1e)))
print('16진수(0x1e) -> 10진수: {}'.format(int(0x1e)))