centa   3년 전

제가 프로그램을 잘 못짜서 그런거같습니다.

어떤식으로 생각하고 바꾸어나가야 효율적인 프로그램을 짤 수 있는지 

제가 짠 프로그램을 바탕으로 부족한점과 개선할점이 알고 싶습니다. 

wider93   3년 전

13, 14번 줄이 있으므로 9번 조건문은 필요가 없습니다. 혹은 cnt 변수도 아예 사용하지 않고 바로 13번 줄에서 check를 +1해줘도 되겠네요.

이상은 알고리즘상의 변경 없이 고칠 수 있는 부분들이었고, 시간을 획기적으로 줄이고 싶으시다면  좀더 수정이 필요합니다. 가령 테스트케이스마다 계산을 반복적으로 하는 대신 123456 ×2까지의 소수를 다 찾아두면 좋을 것입니다. 또 에라토스테네의 체를 이용하면 소수 p의 배수들을 O(n)이 아닌 O(n/p)에 할 수 있어 시간이 많이 줄어듭니다.

centa   3년 전

선생님 감사합니다.

선생님께서 주신 조언으로 만든 프로그램입니다!  

[케이스따라 만드는게아니라 소수를 만들어놓고 시작하자]

[에라토스테네스의 체] 

나무만보고 숲을 보지못한거같습니다.

감사합니다!

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