
"""simple docstring"""




from __future__ import annotations



def 							a__ (				lowerCAmelCase	:       str       ,    lowerCAmelCase	:       str		):






					'''simple docstring'''
					UpperCAmelCase__							: Tuple 							=						get_failure_array(lowerCAmelCase		)

					# 2) Step through text searching for pattern
					UpperCAmelCase__							: Any 							=						0, 0  # index into text, pattern
					while i < len(lowerCAmelCase		):
										if pattern[j] == text[i]:
															if j == (len(lowerCAmelCase		) - 1):
																				return True
															j += 1

										# if this is a prefix in our pattern
										# just go back far enough to continue
										elif j > 0:
															UpperCAmelCase__							: Optional[Any] 							=						failure[j - 1]
															continue
										i += 1
					return False



def 							a__ (				lowerCAmelCase	:       str		):






					'''simple docstring'''
					UpperCAmelCase__							: Union[str, Any] 							=						[0]
					UpperCAmelCase__							: int 							=						0
					UpperCAmelCase__							: List[Any] 							=						1
					while j < len(lowerCAmelCase		):
										if pattern[i] == pattern[j]:
															i += 1
										elif i > 0:
															UpperCAmelCase__							: Union[str, Any] 							=						failure[i - 1]
															continue
										j += 1
										failure.append(lowerCAmelCase		)
					return failure


if __name__ == "__main__":
				# Test 1)
				A__      :	Tuple          =    """abc1abc12"""
				A__      :	Tuple          =    """alskfjaldsabc1abc1abc12k23adsfabcabc"""
				A__      :	List[Any]          =    """alskfjaldsk23adsfabcabc"""
				assert kmp(pattern, texta) and not kmp(pattern, texta)

				# Test 2)
				A__      :	str          =    """ABABX"""
				A__      :	List[str]          =    """ABABZABABYABABX"""
				assert kmp(pattern, text)

				# Test 3)
				A__      :	Optional[int]          =    """AAAB"""
				A__      :	Optional[int]          =    """ABAAAAAB"""
				assert kmp(pattern, text)

				# Test 4)
				A__      :	Union[str, Any]          =    """abcdabcy"""
				A__      :	Tuple          =    """abcxabcdabxabcdabcdabcy"""
				assert kmp(pattern, text)

				# Test 5)
				A__      :	Tuple          =    """aabaabaaa"""
				assert get_failure_array(pattern) == [0, 1, 0, 1, 2, 3, 4, 5, 2]





"""simple docstring"""




from math import isqrt



def 							a__ (				lowerCAmelCase	:       int		):






     '''simple docstring'''
     UpperCAmelCase__							: Tuple 							=						[True] * max_number
     for i in range(2       ,    isqrt(max_number - 1		) + 1		):
          if is_prime[i]:
               for j in range(i**2       ,    lowerCAmelCase       ,    lowerCAmelCase		):
                    UpperCAmelCase__							: List[Any] 							=						False

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



def 							a__ (				lowerCAmelCase	:       int = 10**8		):






     '''simple docstring'''
     UpperCAmelCase__							: Dict 							=						calculate_prime_numbers(max_number // 2		)

     UpperCAmelCase__							: Optional[int] 							=						0
     UpperCAmelCase__							: Optional[int] 							=						0
     UpperCAmelCase__							: Tuple 							=						len(lowerCAmelCase		) - 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


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



