골드바흐 파티션을 찾는 알고리즘으로
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까지 추가시켰음에도 시간초과가 납니다.
제 알고리즘에서 시간을 줄일 수 있는 부분이있는지, 새로 짜야한다면 어떻게 짜는게 좋을지 조언을 부탁드립니다.
시간내주셔서 감사합니다.
1.범위가 작고 쿼리가 여러개이므로 숫자 범위 내의 소수를 미리 구해놓으시면 쿼리마다 소수를 구하지 않으셔도 됩니다.
2.에라토스테네스의 체를 검색해서 공부해보세요.
답변감사합니다!!
소수를 10000까지 미리 구해놓고 findp함수를 한번만 돌아가게 만드니 시간초과를 해결할 수 있었습니다.
그런데 에라토스테네스의 체를 제가 findp함수로 구현했는데 이렇게 구현하는것이 시간복잡도가 높은것인가요?
1씩 증가시키지 않고 i*i부터 i씩 증가시키면서 검사하셔도 충분합니다.
댓글을 작성하려면 로그인해야 합니다.
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까지 추가시켰음에도 시간초과가 납니다.
제 알고리즘에서 시간을 줄일 수 있는 부분이있는지, 새로 짜야한다면 어떻게 짜는게 좋을지 조언을 부탁드립니다.
시간내주셔서 감사합니다.