project euler problem 187 https projecteuler netproblem187 a composite is a number containing at least two prime factors for example 15 3 x 5 9 3 x 3 12 2 x 2 x 3 there are ten composites below thirty containing precisely two not necessarily distinct prime factors 4 6 9 10 14 15 21 22 25 26 how many composite integers n 108 have precisely two not necessarily distinct prime factors returns prime numbers below maxnumber see https en wikipedia orgwikisieveoferatosthenes slowcalculateprimenumbers10 2 3 5 7 slowcalculateprimenumbers2 list containing a bool value for every number below maxnumber2 mark all multiple of i as not prime returns prime numbers below maxnumber see https en wikipedia orgwikisieveoferatosthenes calculateprimenumbers10 2 3 5 7 calculateprimenumbers2 list containing a bool value for every odd number below maxnumber2 mark all multiple of i as not prime using list slicing same as maxnumber i2 2 i 1 but faster than lenisprimei2 2 i returns the number of composite integers below maxnumber have precisely two not necessarily distinct prime factors slowsolution30 10 returns the number of composite integers below maxnumber have precisely two not necessarily distinct prime factors whilesolution30 10 returns the number of composite integers below maxnumber have precisely two not necessarily distinct prime factors solution30 10 benchmarks running performance benchmarks slowsolution 108 50874730000032 whilesol 28 09581200000048 solution 25 063097400000515 returns prime numbers below max_number see https en wikipedia org wiki sieve_of_eratosthenes slow_calculate_prime_numbers 10 2 3 5 7 slow_calculate_prime_numbers 2 list containing a bool value for every number below max_number 2 mark all multiple of i as not prime returns prime numbers below max_number see https en wikipedia org wiki sieve_of_eratosthenes calculate_prime_numbers 10 2 3 5 7 calculate_prime_numbers 2 list containing a bool value for every odd number below max_number 2 mark all multiple of i as not prime using list slicing same as max_number i 2 2 i 1 but faster than len is_prime i 2 2 i returns the number of composite integers below max_number have precisely two not necessarily distinct prime factors slow_solution 30 10 returns the number of composite integers below max_number have precisely two not necessarily distinct prime factors while_solution 30 10 returns the number of composite integers below max_number have precisely two not necessarily distinct prime factors solution 30 10 benchmarks running performance benchmarks slow_solution 108 50874730000032 while_sol 28 09581200000048 solution 25 063097400000515
from math import isqrt


def slow_calculate_prime_numbers(max_number: int) -> list[int]:
    

    
    is_prime = [True] * max_number

    for i in range(2, isqrt(max_number - 1) + 1):
        if is_prime[i]:
            
            for j in range(i**2, max_number, i):
                is_prime[j] = False

    return [i for i in range(2, max_number) if is_prime[i]]


def calculate_prime_numbers(max_number: int) -> list[int]:
    

    if max_number <= 2:
        return []

    
    is_prime = [True] * (max_number // 2)

    for i in range(3, isqrt(max_number - 1) + 1, 2):
        if is_prime[i // 2]:
            
            is_prime[i**2 // 2 :: i] = [False] * (
                
                
                len(range(i**2 // 2, max_number // 2, i))
            )

    return [2] + [2 * i + 1 for i in range(1, max_number // 2) if is_prime[i]]


def slow_solution(max_number: int = 10**8) -> int:
    

    prime_numbers = slow_calculate_prime_numbers(max_number // 2)

    semiprimes_count = 0
    left = 0
    right = len(prime_numbers) - 1
    while left <= right:
        while prime_numbers[left] * prime_numbers[right] >= max_number:
            right -= 1
        semiprimes_count += right - left + 1
        left += 1

    return semiprimes_count


def while_solution(max_number: int = 10**8) -> int:
    

    prime_numbers = calculate_prime_numbers(max_number // 2)

    semiprimes_count = 0
    left = 0
    right = len(prime_numbers) - 1
    while left <= right:
        while prime_numbers[left] * prime_numbers[right] >= max_number:
            right -= 1
        semiprimes_count += right - left + 1
        left += 1

    return semiprimes_count


def solution(max_number: int = 10**8) -> int:
    

    prime_numbers = calculate_prime_numbers(max_number // 2)

    semiprimes_count = 0
    right = len(prime_numbers) - 1
    for left in range(len(prime_numbers)):
        if left > right:
            break
        for r in range(right, left - 2, -1):
            if prime_numbers[left] * prime_numbers[r] < max_number:
                break
        right = r
        semiprimes_count += right - left + 1

    return semiprimes_count


def benchmark() -> None:
    
    
    
    
    

    from timeit import timeit

    print("Running performance benchmarks...")

    print(f"slow_solution : {timeit('slow_solution()', globals=globals(), number=10)}")
    print(f"while_sol     : {timeit('while_solution()', globals=globals(), number=10)}")
    print(f"solution      : {timeit('solution()', globals=globals(), number=10)}")


if __name__ == "__main__":
    print(f"Solution: {solution()}")
    benchmark()