success - Baekjoon 9단계-3 / 11653번 소인수분해 python3

• 2월3일(fail-invalid)

흠... 코드는 일단 이렇게 짯다..

 

https://github.com/cyanindy/baekjoon_online_judge/blob/main/python3/step9/11653.py

GitHub - cyanindy/baekjoon_online_judge: https://www.acmicpc.net/

 

문제가 이건데

 

 

 

그래서 이전에 했던

소수 판별을 가져와서,

 

입력이 정수 1에서 천만까지고

소수*소수에서 천만이 안넘어야 한다는거였는데

 

그래서 처음에는 저 코드에서 소수 리스트를 짤 때

소수 범위를 3163까지만 판별했었다.

3162^이 천만을 안넘어서...

 

 

근데 생각해보니까 더 위의 수로 해서 2도 소수니까

만약에 4백만 뭐시기가 되는 소수가 있고, 2랑 곱하면? 천만이 안되는거임

 

ㅅㅂ 그럼 5백만까지의 모든 수를 소수인지 판별해야댐?

시간 너무 오래걸릴거같은데...

 

일단 해봐야겠다

 

계속 돌아간다...

 

안나온다..

 

접근이 틀린건가

 

후 가면갈수록 어렵구만

 

 

 

 

 

 

• 2월9일(fail-timeover)

기존코드

 

https://www.acmicpc.net/problem/11653

def pn(num) :
    f=0
    if num==1 : return f
    for j in range(2,num) :
        if j*j<=num :
            if num%j==0 : return f
    return num

def fz(num) :
    for i in range(0,len(pn_ls)) :
        v=int(num/pn_ls[i])
        #print("v: ",v," pn_ls[i]: ",pn_ls[i]," num: ",num)
        if num%pn_ls[i]==0 :
            ls.append(pn_ls[i])
            if v==1 :
                break
            else :
                #print("run fz")
                fz(v); break
        else : pass
    return ls

ls=[]
pn_ls=[]
ck_n=0
for i in range(2,3163) :
    ck_n=int(pn(i))
    if ck_n != 0 : pn_ls.append(ck_n)
    else : pass


n=int(input())
if n==1 : pass
else :
    result=fz(n)
    for i in result :
        print(i)

 

가 이건데 틀렷다고 나왔다

일단 간과한게

소인수분해이고 문제의 숫자 제한이 천만이니까

2*4백만대의 소수 의 경우의 수를 생각했어야 했는데

3163의 제곱이 천만 조금 안되서 소수 범위로 잡았었다.

 

자 그렇다면

이제 소수 범위가 잘못되서 틀렸다고 나온걸 알았으니

저 범위를 499만9999로 바꿔서 채점하기로 들어간다면

일단 시간초과는 나올것같지만 접근은 맞았다고 생각되서 돌려보았따

 

ls=[]
pn_ls=[]
ck_n=0
for i in range(2,4999999) :
    ck_n=int(pn(i))
    if ck_n != 0 : pn_ls.append(ck_n)
    else : pass

 

이렇게 바꿔서 해보았더니

 

시간초과

이제 소수 구하는 범위는 알았으니

5백만개 수를 일일히 훑을수는 없으니

 

에라토스테네스의 체를 이용해서 소수리스트를 만들어봐야겠다

 

#https://www.acmicpc.net/problem/11653

def fz(num) :
    for i in pn_ls :
        v=int(num/i)
        if num%i==0 :
            ls.append(i)
            if v==1 :
                break
            else :
                fz(v); break
    return ls

pn_ls=[]
ls=[]
a=[False,False]+[True]*4999999
for o in range(2,4999999) :
    if a[o] :
        pn_ls.append(o)
        for j in range(o*2,4999999,o) :
            a[j]=False
    else : pass

n=int(input())
if n==1 : pass
else :
    result=fz(n)
    for i in result :
        print(i)
        
#print(pn_ls[:20])
#print(ls)

 

대충 이렇게 만들어봤고

결과도 잘 나오는데...

 

뭐가 잘못된걸까... ㅠㅠ

 

 

 

 

 

• 2월10일(success)

백준에 질문글을 올렸는데 두분이서 너무 친절하게 도와주셧다 ㅠㅠ

https://www.acmicpc.net/board/view/83439

글 읽기 - python3 틀렸습니다 반례 찾아주실분...?

일단 시간초과가 나는건

n 의 제곱근까지 만 소수인지 판별하면 n은 소수라는 걸로 판별이 가능하고

그에 따라서 내가 썻던 코드에서 소수 리스트를 1천만 까지 구할 필요도 없게된다

천만의 제곱근의 3162까지의 소수만 구해서

얘네로 안나눠지면 그 수는 소수인거임

 

통과 코드

https://github.com/cyanindy/baekjoon_online_judge/blob/main/python3/step9/11653.py

GitHub - cyanindy/baekjoon_online_judge: https://www.acmicpc.net/

 

ㅅㅂㅋㅋ

 

어렵다어려워