문제에 대한 풀이는 대부분 비슷한것 같으니, 따로 서술하지 않겠다.
처음에 sqrt(B)까지 Sieve of eratosthenes 알고리즘을 돌린다.
돌린 후, 1부터 sqrt(B)까지 순회를 돌리며 소수만 고려해준다.
어떤 분의 말에 의하면 1부터 B까지의 소수 개수는 대충 sqrt(B)개로 생각하고 계산하면 된다고한다.
즉, sqrt(B) 중 소수의 개수는 sqrt(sqrt(B))개 이다.
이제 각 소수마다 소수 x가 있을 때,
B보다 작을 때까지 x를 계속 곱해나간다.
즉, 각 소수마다 logB번 반복해서 곱한다.
(로그의 성질에 의해 로그의 밑은 생략한다.)
시간복잡도를 따지면 O(sqrt(B)*log(log(sqrt(B))) + sqrt(B) + sqrt(sqrt(B))*logB) =
O(sqrt(B)*log(log(sqrt(B))) + sqrt(sqrt(B))*logB) 이다.
최악인 B = 10^14를 대입해서 계산하면 2억(시간제한:2초) 이하이므로
시간안에 해결됨을 알 수 있다.