sol1.py

"""
Project Euler Problem 800: https://projecteuler.net/problem=800

An integer of the form p^q q^p with prime numbers p != q is called a hybrid-integer.
For example, 800 = 2^5 5^2 is a hybrid-integer.

We define C(n) to be the number of hybrid-integers less than or equal to n.
You are given C(800) = 2 and C(800^800) = 10790

Find C(800800^800800)
"""

frommathimportisqrt, log2


defcalculate_prime_numbers(max_number: int) ->list[int]:
"""
 Returns prime numbers below max_number

 >>> calculate_prime_numbers(10)
 [2, 3, 5, 7]
 """

is_prime= [True] *max_number
foriinrange(2, isqrt(max_number-1) +1):
ifis_prime[i]:
forjinrange(i**2, max_number, i):
is_prime[j] =False

return [iforiinrange(2, max_number) ifis_prime[i]]


defsolution(base: int=800800, degree: int=800800) ->int:
"""
 Returns the number of hybrid-integers less than or equal to base^degree

 >>> solution(800, 1)
 2

 >>> solution(800, 800)
 10790
 """

upper_bound=degree*log2(base)
max_prime=int(upper_bound)
prime_numbers=calculate_prime_numbers(max_prime)

hybrid_integers_count=0
left=0
right=len(prime_numbers) -1
whileleft<right:
while (
prime_numbers[right] *log2(prime_numbers[left])
+prime_numbers[left] *log2(prime_numbers[right])
>upper_bound
 ):
right-=1
hybrid_integers_count+=right-left
left+=1

returnhybrid_integers_count


if__name__=="__main__":
print(f"{solution() =}")