공부하기싫어
article thumbnail
  • 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/

https://www.acmicpc.net/ . Contribute to cyanindy/baekjoon_online_judge development by creating an account on GitHub.

github.com

 

문제가 이건데

 

 

 

그래서 이전에 했던

소수 판별을 가져와서,

 

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

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

 

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

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

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

 

 

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

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

 

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

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

 

일단 해봐야겠다

 

계속 돌아간다...

 

안나온다..

 

접근이 틀린건가

 

후 가면갈수록 어렵구만

 

 

 

 

 

 

  • 2월9일(fail-timeover)

기존코드

 

<python />
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로 바꿔서 채점하기로 들어간다면

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

 

<python />
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백만개 수를 일일히 훑을수는 없으니

 

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

 

<python />
#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 틀렸습니다 반례 찾아주실분...?

댓글을 작성하려면 로그인해야 합니다.

www.acmicpc.net

일단 시간초과가 나는건

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/

https://www.acmicpc.net/ . Contribute to cyanindy/baekjoon_online_judge development by creating an account on GitHub.

github.com

 

ㅅㅂㅋㅋ

 

어렵다어려워