4948번 - 베르트랑 공준
에라토스테네스의 체로 소수를 구하고 prime_num이라는 리스트에 저장 후
prime_num 이랑 n+1~2n의 리스트를 집합으로 바꾸어 둘의 교집합의 길이를 구하는 식으로
코드를 짰는데 예제 마지막 숫자인 100000에서 시간이 많이 걸렸습니다.
아직 초보라서 어느 부분을 고쳐야 할 줄 잘 몰라 질문 드립니다...
잘못된 부분이나 시간을 절약할 수 있는 부분 조언 부탁드립니다.
우선 이게 전체 코드이면 문제를 잘못 이해하신 것 같고, 전체 코드가 아니라면 어디서 시간이 오래 걸리는지 알기 어렵기 때문에 전체를 올려주시기 바랍니다.
이게 전체이고 입력이 제대로 된다고 가정하면 remove(i)와 A&R에서 오래 걸리는 거 같네요.
i가 소수이면 arr[i]가 True인 리스트를 만드는 방법으로 코드를 작성하면 문제를 해결할 수 있을 겁니다.
댓글을 작성하려면 로그인해야 합니다.
bsw3232 1년 전
에라토스테네스의 체로 소수를 구하고 prime_num이라는 리스트에 저장 후
prime_num 이랑 n+1~2n의 리스트를 집합으로 바꾸어 둘의 교집합의 길이를 구하는 식으로
코드를 짰는데 예제 마지막 숫자인 100000에서 시간이 많이 걸렸습니다.
아직 초보라서 어느 부분을 고쳐야 할 줄 잘 몰라 질문 드립니다...
잘못된 부분이나 시간을 절약할 수 있는 부분 조언 부탁드립니다.