





'''simple docstring'''




import math







def _lowerCAmelCase     (      _lowerCAmelCase    )->     list[int]:
 __UpperCAmelCase					=   []
 __UpperCAmelCase					=   2
 __UpperCAmelCase					=   int(math.sqrt(_lowerCAmelCase    )    )  # Size of every segment
 __UpperCAmelCase					=   [True] * (end + 1)
 __UpperCAmelCase					=   []

 while start <= end:
  if temp[start] is True:
   in_prime.append(_lowerCAmelCase    )
   for i in range(start * start       ,    end + 1       ,    _lowerCAmelCase    ):
    __UpperCAmelCase					=   False
  start += 1
 prime += in_prime

 __UpperCAmelCase					=   end + 1
 __UpperCAmelCase					=   min(2 * end       ,    _lowerCAmelCase    )

 while low <= n:
  __UpperCAmelCase					=   [True] * (high - low + 1)
  for each in in_prime:
   __UpperCAmelCase					=   math.floor(low / each    ) * each
   if t < low:
    t += each

   for j in range(_lowerCAmelCase       ,    high + 1       ,    _lowerCAmelCase    ):
    __UpperCAmelCase					=   False

  for j in range(len(_lowerCAmelCase    )    ):
   if temp[j] is True:
    prime.append(j + low    )

  __UpperCAmelCase					=   high + 1
  __UpperCAmelCase					=   min(high + end       ,    _lowerCAmelCase    )

 return prime

print(sieve(10**6))












'''simple docstring'''




from __future__ import annotations







def _lowerCAmelCase     (      _lowerCAmelCase    )->     int:
 if not nums:
  return 0
 __UpperCAmelCase					=   nums[0]
 __UpperCAmelCase					=   0
 for num in nums[1:]:
  __UpperCAmelCase					,    __UpperCAmelCase					=   (
      max_excluding + num,
      max(_lowerCAmelCase       ,    _lowerCAmelCase    ),
  )
 return max(_lowerCAmelCase       ,    _lowerCAmelCase    )


if __name__ == "__main__":
    import doctest

    doctest.testmod()





