adasd

def sieve_of_atkin(limit):
    """
    Implements the Sieve of Atkin to generate prime numbers up to a given limit.
    Returns a list of prime numbers.
    """
    if limit < 2:
        return []

    primes = [False] * (limit + 1)
    primes[2] = primes[3] = True  # Marking 2 and 3 as prime

    for x in range(1, int(limit ** 0.5) + 1):
        for y in range(1, int(limit ** 0.5) + 1):
            n = (4 * x * x) + (y * y)
            if n <= limit and (n % 12 == 1 or n % 12 == 5):
                primes[n] = not primes[n]

            n = (3 * x * x) + (y * y)
            if n <= limit and n % 12 == 7:
                primes[n] = not primes[n]

            n = (3 * x * x) - (y * y)
            if x > y and n <= limit and n % 12 == 11:
                primes[n] = not primes[n]

    for i in range(5, int(limit ** 0.5) + 1):
        if primes[i]:
            for j in range(i * i, limit + 1, i * i):
                primes[j] = False

    # Extract the list of primes
    return [num for num, is_prime in enumerate(primes) if is_prime]


def select_prime(primes, min_value=1000):
    """
    Picks a prime number from the list that is >= min_value.
    If no such prime exists, return the largest prime found.
    """
    for prime in primes:
        if prime >= min_value:
            return prime
    return primes[-1] if primes else None  # Handle case if primes list is empty


def polynomial_rolling_hash(string, modulus, base=31):
    """
    Implements polynomial rolling hashing for a given string.
    Uses the provided modulus and a prime base (default 31).
    """
    hash_value = 0
    power = 1  # Tracks base^i

    for char in string:
        hash_value = (hash_value + (ord(char) * power)) % modulus
        power = (power * base) % modulus  # Update base power

    return hash_value


if __name__ == '__main__':
    # Generate primes using the Sieve of Atkin
    primes = sieve_of_atkin(10000)  # Modify limit as needed

    # Select a prime modulus
    modulus = select_prime(primes, 1000)
    
    if modulus is None:
        raise ValueError("No suitable prime modulus found!")

    # Sample strings to hash
    test_strings = ["alpha", "beta", "gamma", "delta", "epsilon"]

    # Compute and print hash values
    for string in test_strings:
        hash_value = polynomial_rolling_hash(string, modulus)
        print(f"Hash of '{string}' is {hash_value}")