[제로베이스] CH2. 기초 수학 - 약수, 소수, 소인수분해

약수

어떤 수를 나누어떨어지게 하는 수

10÷1=10
10÷2=5
10÷3=3 ··· 1
10÷4=2 ··· 2
10÷5=2
10÷6=1 ··· 4
10÷7=1 ··· 3
10÷8=1 ··· 2
10÷9=1 ··· 1
10÷10=1

이처럼, 10을 나누어 떨어지게 하는 1, 2, 5, 10이 10의 약수입니다.

약수 구하기(파이썬)

num = int(input("정수 입력 : "))

for i in range(1, num+1):
    # 나누어 떨어진다면 약수임
    if num % i == 0:
        print(i, end=' ')

소수

1과 자기자신 외에는 어떠한 수로도 나누어 떨어지지 않는 수를 말한다. 즉, 1과 자신만을 약수로 가지는 수(단, 1은 제외).

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59....

소수 판별(파이썬)

### 반복문으로 만들기 ###
i = 2
while(i < num):
    if num % i == 0:
        print('소수가 아닙니다')
        break
    else:
        i += 1
        
if i == num :
    print('소수입니다.')

### 함수로 만들기 ###
def is_prime_num(n):
    for i in range(2, n):
        if n % i == 0:
            return False # i로 나누어 떨어지면 소수가 아니므로 False 리턴
    
    return True # False가 리턴되지 않고 for문을 빠져나왔다면 소수이므로 True 리턴

소수 구하기(에라토스테네스의 체)

1. 2 ~ N까지의 범위가 담긴 배열을 만든다.

2. 해당 배열 내의 가장 작은 수 i 부터 시작하여, i의 배수들을 해당 배열에서 지워준다. (i는 소수이기 때문에 i자체는 지우지 않는다.)

3. 주어진 범위 내에서 i의 배수가 모두 지워지면 i 다음으로 작은 수의 배수를 같은 방식으로 배열에서 지워준다.

4. 더 이상 반복할 수 없을 때까지 2, 3번의 과정을 반복해준다.

def is_prime_num(n):
    arr = [True] * (n + 1) # 특정 수가 지워졌는지 아닌지 확인하기 위한 배열
    arr[0] = False
    arr[1] = False

    for i in range(2, n + 1):
        if arr[i] == True: # 특정 수가 지워지지 않았다면 (소수여서)
            j = 2

            while (i * j) <= n:
                arr[i*j] = False # i의 배수의 값을 False로 지워준다.
                j += 1

    return arr

arr = is_prime_num(50) # 0 ~ 50중 소수를 구하기 위한 함수

for i in range(len(arr)):
    if arr[i] == True:
        print(i, end=' ')

소인수

소인수란 주어진 자연수를 나누어 떨어뜨리는 약수 중에서 소수(2, 3, 5, 7....)인 약수를 말한다.

소인수 분해

1보다 큰 자연수를 소인수만의 곱으로 나타낸 것.
ex) 30 -> 2 x 3 x 5

소인수 분해(파이썬)

num = int(input())

n = 2
while (n <= num):
	if num % n == 0 :
    	print(f'소인수 : {n}')
        num /= n
	else:
    	n += 1

소인수 분해 응용

제곱이 되게하는 수 구하기
N에 x를 곱하면 y의 제곱이 된다고 할때 x의 가장 작은 정수를 구하시오.

num = 10

n = 2
numbers = []
while (n <= num):
    if num % n == 0 :
        print(f'소인수 : {n}')
        if (n in numbers):
            numbers.remove(n)
        else:
            numbers.append(n)
        num /= n
    else:
        n += 1
        
result = 1
for i in numbers:
    result *=  i
    
print(f'Need number is : {result}')