파이썬 알고리즘 105 번 | [백준 11653번] 소인수분해

105. 큰 수 소인수분해

1) 어떤 전략(알고리즘)으로 해결?

• 위처럼 해당 수까지 소수들을 체크해내는 배열을 arr 을 생성해놓는다
  이후 arr 배열에서 0으로 체크된 소수들만 빼서 새로운 배열 sosu 에 저장한다.

• 1) n을 sosu에 있는 아이들로 나눠보면서 나머지가 0이 되는 경우가 발생한다면

  • sosu에 있는 아이를 final 배열에 저장, final 인덱스 갱신

• 2) 그리고 이제 n을 몫으로 갱신해서 또다시 1의 과정을 반복

=> 허나 위 방법은 너무 시간이 오래 걸린다. 더 짧은 시간을 들여서 소인수분해를 진행하는 방법은 없을까?

이중 for 문을 쓰지않고 직관적으로 할 순 없나?????

• 소인수분해를 한다치면 주어진 숫자 n을 소수로 나눠보면서 나눠떨어지는 소수가 있을 때까지 하는 건데..

2) 코딩 설명

n=int(input())
if n !=0 :
    arr=[0]*(n+1)

    for i in range(2,n+1) :
        if arr[i]==0:
            for j in range(i,n+1,i):
                arr[j]=1
            arr[i]=0

위 코드는 2부터 입력된 숫자까지 중 소수에다가 체크 표시하는 것

<내 풀이>

n=int(input())
d=2
while n>=2:
    if n%d==0:
        n//=d
        print(d)
    else : 
        d+=1

=> 나는 소수로만 나누려고 생각을 했는데 굳이 안그래도 된다. 어차피 소수로 나눠지게 되어있다

<다른 분의 풀이 or 내 틀린 풀이, 문제점>

출처 : 출처

n=int(input())
indexofSosu = 0
sosuNum = 0
indexofFinal = 0

if n !=0 :
    arr=[0]*(n+1)
    sosu = [0]*(n+1)
    final = [0]*(n+1)

    for i in range(2,n+1) :
        if arr[i]==0:
            for j in range(i,n+1,i):
                arr[j]=1
            arr[i]=0


    for i in range(2,n+1) :
        if arr[i]==0 :
            sosu[indexofSosu] = i
            indexofSosu+=1
            sosuNum +=1
    v=n
    while v >= 2 :
        for i in range(sosuNum) :
            if v%(sosu[i])==0 :
                final[indexofFinal] = sosu[i]
                indexofFinal+=1
                v//=sosu[i]

    final.sort()

    for i in range(indexofFinal,0,-1) :
        print(final[n-i+1])

• 시간 초과가 나온 코드.. for문이 너무 많긴 하다..
  -> 거기다가 sort 함수까지 ㅎㅎ..이게 좀 클드읏..
  -> 그래서 sort함수 안 쓰기 위해서 에라스토테네스에서 했던 것처럼 배열만들고 인덱스로 수를 판단하고, 해당 인덱스 값에는 나타난 수를 쓰기로 했당

n=int(input())
indexofSosu = 0
sosuNum = 0

if n !=0 :
    arr=[0]*(n+1)
    sosu = [0]*(n+1)
    final = [0]*(n+1)

    for i in range(2,n+1) :
        if arr[i]==0:
            for j in range(i,n+1,i):
                arr[j]=1
            arr[i]=0


    for i in range(2,n+1) :
        if arr[i]==0 :
            sosu[indexofSosu] = i
            indexofSosu+=1
            sosuNum +=1
    v=n

    while v >= 2 :
        for i in range(sosuNum) :
            if v%(sosu[i])==0 :
                final[sosu[i]]+=1
                v//=sosu[i]

    for i in range(n+1) : 
        if final[i]!=0:
            for j in range(final[i]) :
                print(i)

<반성 점>

• python 내장 함수 sort의 시간 복잡도가 꽤 크네..

  l.sort(): O(N Log N)

• 애초에 이중 for문 돌면서 그 범위안에 있는 모든 소수를 구하는 것이 시간이 너무 오래 걸리네..

• 너무 어렵게 접근하려하지말자.. 에라스토테네스체도 유도리있게 사용하자..

<배운 점>

• 소인수분해의 성질 : 소수들의 곱으로 이뤄지는 것!

• ZeroDivisionError

  ZeroDivisionError: integer division or modulo by zero
  => 0으로 나누기할 때 나타나는 에러

• 리스트 오름차순 정렬
  파이썬 리스트 오름차순 출처

>>> a = [1, 10, 5, 7, 6]
>>> a.sort()
>>> a
[1, 5, 6, 7, 10]
>>> a = [1, 10, 5, 7, 6]
>>> a.sort(reverse=True)
>>> a
[10, 7, 6, 5, 1]