Project Euler 800 - Hybrid Integers

Official link: https://projecteuler.net/problem=800

Thought Process

With numbers this huge I decided to work with the logarithms instead. We have the following:

The key to this problem is figuring out that, given a prime p if we can find the maximum prime q such that the above inequality fails, then:

  1. If we have equality then there will be π(q) - π(p) pairs (p, q) such that inequality holds

  2. If we have inequality then there will be (π(q) - 1) - π(p) pairs (p, q) such that inequality holds

Therefore we just start at p = 2 and then increment p until 2plog(p) > blog(a), at each increment finding the respective q.

My method of finding q is by using a binary search, we put the lower bound as the next prime after p and an upper bound of alog(b)/log(p) because of the following:

The implementation is slightly different as the binary search may result in a q that satifies the inequality, in this case we take the next prime, I made a function next_prime(n) which helped readability a lot in my code

Interactive Code

Input 2 integers separated by a space (a, b)

Code will output C(a^b)