[백준] 23005. Consecutive Primes

https://www.acmicpc.net/problem/23005

문제 요약

• Z 보다 작거나 같은 수중 가장 큰, 연속하는 소수의 곱 찾기
• Z : 10^18
• TC : 100

접근법

• ${10^9}$까지(더 클 수도 있겠고) 소수를 모두 구한다음에 찾으면 될 것 같음
• 실제로 구해보면 50847534개 나옴
• 구하는 시간 복잡도도 문제지만, 공간 복잡도도 걸림
• 그래서 생각을 전환해봄
• 구하려는 수가 두 소수의 연속 곱이니까 ${\sqrt(Z)}$ 근방의 소수를 이용해보면 될 것 같음 => ${10^9}$
• p가 소수인지 판별하려면 ${\sqrt(p)}$까지 숫자로 나눠보면 되는데, ${10^9}$ 인 경우 31622번 나눠보면 됨
• 다 구할 필요는 없고 "다음번" 소수까지 해보면 되는데 "다음번" 소수가 얼마나 멀리있을까?
• 아까 구해본 ${10^9}$까지 소수 중에서 가장 큰 간격을 찾아보면 282
• 즉 31622번씩 나눠보는 일을 최대 282번 정도(또는 더 많을 수도 있겠지만) 해보면 될 것 같음!
• 위 아래로 282보다 조금 더 여유를 줘서 계산해보면 후보가 되는 소수들을 구할 수 있을 것 같음
• TC가 100개이니까 100 31622 282 * k 정도 연산하면 됨(k는 정하기 나름일 듯)
• 주의할 것은 ${\sqrt(Z)}$ 보다 작은 소수만 보면 안되고 큰 소수도 봐야함. ${\sqrt(Z)}$보다 큰 소수 * 작은 소수를 곱해도 Z보다 같거나 작을 수 있음