[질문] (java) 14622 선생님들 제가 무엇을 잘못한 것일까요

[쿨러는녹투아(sushiomakase)]

백준 14622 소수 게임입니다..생각해보니 문제를 안올렸네요

지금 푼 지 3시간정도 지나서 어느정도 나올만한 오류는 다 해결했는데 그런데도 3%에서 입구컷당하니까 너무 우울합니다

마이너한 문제라서 인터넷에 답도 없다보니 PS갤러리 선생님들의 조언을 구하고 싶읍니다..

이 문제가 차라리 아예 어려웠으면 포기하겠는데 골드3치고 할만한거 같아서 포기도 못하겟읍니다..

이렇게 풀었읍니다..

[익명(182.231)]

문제 번호가 몇번인데요...? - dc App

[쿨러는녹투아(sushiomakase)]

백준 14622 소수 게임입니다 선생님

[쿨러는녹투아(sushiomakase)]

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

[익명(110.9)]

소트하고 0번째거는 왜 지우는거야?

[쿨러는녹투아(sushiomakase)]

길이가 계속 늘어나면 정렬할게 많아져서 시간초과 안날려고 계속 제거해줬어여

[익명(110.9)]

틀린건 에라토스테네스의 체에서 j<500000/i 때문일거 같은데

[익명(110.9)]

for(int i=2; i*i <= 5000000 ; i++){ if(!primeNumber[i]){ for(int j= i*i; j<=5000000 ; j+=i){ primeNumber[j]=true; } } }

[쿨러는녹투아(sushiomakase)]

어??

[쿨러는녹투아(sushiomakase)]

어?????

[쿨러는녹투아(sushiomakase)]

어?????????

[쿨러는녹투아(sushiomakase)]

말할 수 있는 소수는 항상 5000000미만이라고 해서 0~4999999까지만 커버하도록 500만개짜리 리스트 만들고 했었는데 말씀하신 대로 하니까 바로 정답되네요

[익명(110.9)]

소수 500만까지 보려면 j<=5000000까지 값을 다 지워야지

[쿨러는녹투아(sushiomakase)]

계속 생각해봤는데 500만은 어차피 입력으로 안주어지니까 계산 안해도 대는거 아니에여??

[익명(110.9)]

i가 2라고 생각해보자 그럼 j는 250만까지 지우겠지?

[쿨러는녹투아(sushiomakase)]

아

[익명(110.9)]

그럼 그 후 숫자는 소수인지 아닌지 판별을 안해둔건데 i가 2일때도 그러니 i가 커질수록 점점 체크 안한게 많아지겠지

[쿨러는녹투아(sushiomakase)]

와 진짜 다른 곳도 아니고 에라토스테네스의 체에서 실수했을거라고는 상상도 못했는데 진짜 감사합니다 선생님. 선생님 덕분에 그래도 5시간은 넘기지 않고 결국 풀었읍니다. 사랑합니다 감사합니다

[쿨러는녹투아(sushiomakase)]

[익명(110.9)]

그리고 에라토스테네스의 체에서 j는 i*i부터 시작해도 됨 왜냐면 (2,3,4,5,....j-1)*j 는 이미 i가 (2,3,4,...j-1)일 때 다 지운거니까

[쿨러는녹투아(sushiomakase)]

이번에 역대급으로 삽 파면서 '에라토스테네스의 체' 이 친구하나만큼은 제대로 배우고 갑니다..++++