[알고리듬] #48 소인수 분해

파이싼 실습창을 열 수 있습니다.실습창 열기

여유를!

 

 

1. 문제

 99887766을 소인수 분해하세요.

 

2. 문제 분석(problem analysis)

소인수 분해(prime factorization)는 합성수를 소수의 곱의 꼴로 바꾸는 일입니다.

90을 소인수 분해하면 2*3*3*5이됩니다.

• 합성수(composite number)는 1보다 큰 자연수 중에서 소수가 아닌 수로,
  약수의 개수가 3개 이상이고 둘 이상의 소수를 곱한 자연수이다.
• 소수(Prime Number)는 1과 자기 자신 만을 약수로 가지는 수이다

 

 

3. 알고리듬 설계(algorithm design)

90을 예로 들겠습니다.

• 90을 2로 나누어봅니다.
• 나누어지면 2를 모으고, 몫인 45를 또 2로 나누어 봅니다. 이 과정을 반복합니다.
• 나누어지지 않으면 2를 3으로 바꾸어 45를 나누어 봅니다. 나누어지면 3을 모으고 몫인 15를 또 3으로 나누어 봅니다.
• 이와같은 과정을 몫이 나누는 수보다 크거나 같은 동안 반복합니다. 
• 같은 경우는 마지막 몫을 모으기 위한것입니다.

이해를 돕기 위하여 순서도를 그렸습니다.

숫자를 대입하여 가면서 이해가 될때까지 분석하세요. 

 

4, 코딩

다음은 코딩의 예입니다.

스스로 코딩한 다음에 비교하여 보세요.

num=99887766
n=num
p=[]
f=2
while n>=f:
    while n%f==0:
        p.append(f)  
        n//=f
    f+=1
r='*'.join(map(str,p))     # list의 int item을 str으로 바꿈
print(f'{num} = {r}')

'''
11번 줄은 다음과 같이 코딩할 수 있습니다.
print('{} = {}'.format(num,r))
'''

 

조금 어렵습니다.

우리는 Top Genius!

하면 됩니다.

 

안녕!