[Python] 소인수 분해 (** 연산자, // 연산자)

소인수 분해는 한 합성수를 소수들의 곱으로 표현하는 방법을 말한다

 

가장 간단한 방법은

2부터 시작해 n의 소인수가 될 수 있는 수들을 순회하면서, n의 약수를 찾을 때마다 나누는 방법이 있다

n이 소수인 경우 √n번 반복문을 돌기 때문에 시간 복잡도는 O(√n)이 된다

이 범위의 소수들을 미리 찾아둔다면, 훨씬 빨라지는 최적화 방법이 될 것이다

 

코드는 다음과 같다

 

N = int(input())

for i in range(2, int(N ** 0.5) + 1): #math.sqrt() 대신 **0
    5
    while(N > 1):
        if(N % i == 0):
            N //= i #정수형 나눗셈
            print(i)
        else:
            break

if(N > 1): print(N)

 

1. ** 연산자

제곱근 값을 구할 때, 다음과 같이 math 모듈을 import하여 할 수 있다

import math
~
sqrtN = int(math.sqrt(N))

하지만 제곱근은 ^(1/2)과 의미가 같기 때문에,

sqrtN = N**(1/2)

로 표현할 수 있다

 

2. // 연산자

/ 연산자는 파이썬에서 실수형 나눗셈이기 때문에, 후에 int(a / b) 정수형 변환을 해주어야 한다

이를 간단히 표현하기 위해 정수형 나눗셈 연산자 //가 따로 있다

a = 3 // 2
a
>> 1

 

- https://snupi.tistory.com/74?category=885572