구글링을 하면 어느 프로그래밍 언어든
어떤 수가 소수인지 알려주는 함수와,
어떤 수를 소인수분해 해주는 함수를 매우 쉽게 찾을 수 있습니다.
그러면 앞의 두 함수를 날로먹어서 어떤 수 n을 넣었을때 약수를 구하고,
모든 약수에 대해 d+n/d 가 소수인지 알려주는 함수를 만들 수 있습니다.
이제 이 함수에다가 n을 1부터 100000까지 대입해 주면 되겠네요 (물론 반복문으로)
-
저는 왜 소수인지 알려주는 함수와 소인수분해 해주는 함수를 쉽게 찾을 수 없는거죠....참고로 c입니다-
(시즌 1인줄 알고 써서ㅋㅋㅋㅋ 다시 쓰네요)
소수인지 알려주는 함수와 소인수분해 해주는 함수는 필요가 없습니다.
한 가지 관찰을 하게 되면 문제가 굉장히 쉬워지는데, 스포일테니 비댓으로 남겨놓겠습니다.
n이 아무리 커봐야 100000이기 때문에 어느 정도 널널한 편입니다 (시즌1 14번은..ㅋㅋㅋ)
그렇다고 해서 1~n까지 전부 다 확인하면서 약수인지 판별하는건 좋은 선택이 아닐겁니다.
(오래걸리니까요. 물론 뭐라도 해서 답을 구해야한다면 괜찮은 선택지입니다)
제가 비댓으로 써둘 관찰을 하면 1~sqrt(n)(루트n)까지만 돌려봐도 됩니다.
100000*sqrt(100000)은 1초 안에도 아마 돌거에요.
(아 잊었는데 소수인지 확인하는 것은 에라토스테네스의 체로 미리 구해두면 됩니다)
흠 쓰고 보니까 너무 난해한데 코드를 어떻게 짜는지, 방법이 어떻게 돌아가는지 등등 자유롭게 질문해주시면 제 능력이 되는 데까지.. 답변해 드리겠습니다
- 시즌1 15번 포기하고 가끔씩 올라오는 미궁 질문글에 서식하는 1ㅅ 드림 -
좋아요0 -
비밀 댓글이 등록 되었습니다!
-
오오오오ㅇ
이런 방법이 있다니.....
사실 저도 수학자 15번은 cospi님한테 거의 힌트 다 받아서 풀었어요좋아요0
-
