choah76   3년 전

골드바흐 파티션을 찾는 알고리즘으로 

1. 주어진 N을2로 나눈수가 소수일경우 : 골드바흐 파티션은 N/2 N/2로 출력한다.

2. 만약 2로 나눈 수가 소수가 아닐 경우

          2-1. A = N/2, B = N/2를 만들고, while문을 통해 A,B 모두 소수가 될때까지 A -=1, B+=1 반복 (시간초과 발생하여 개선함)

          2-1. N/2 미만의 가장 큰 소수를 A로 하고, B = N-A라 한다.

          2-2. N미만의 소수들을 원소로하는 리스트 L에서 A의 인덱스를 확인하고, while문을 통해 A,B모두 소수가 될 때까지 A의 인덱스를 -1 한다.

현재 2-2알고리즘에서도 시간초과가 발생하여, 빠른A+B 문제처럼 sys.stdin.readline까지 추가시켰음에도 시간초과가 납니다.

제 알고리즘에서 시간을 줄일 수 있는 부분이있는지, 새로 짜야한다면 어떻게 짜는게 좋을지 조언을 부탁드립니다.

시간내주셔서 감사합니다.                         

shg9411   3년 전

1.범위가 작고 쿼리가 여러개이므로 숫자 범위 내의 소수를 미리 구해놓으시면 쿼리마다 소수를 구하지 않으셔도 됩니다.

2.에라토스테네스의 체를 검색해서 공부해보세요.

choah76   3년 전

답변감사합니다!!

소수를 10000까지 미리 구해놓고 findp함수를 한번만 돌아가게 만드니 시간초과를 해결할 수 있었습니다.

그런데 에라토스테네스의 체를 제가 findp함수로 구현했는데 이렇게 구현하는것이 시간복잡도가 높은것인가요?

shg9411   3년 전

1씩 증가시키지 않고 i*i부터 i씩 증가시키면서 검사하셔도 충분합니다.

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