Программа не успевает по времени. Задача "Максимальное удивление"

[Alexa]

Windows
Python 3.9.5
мой код:

import math
def qwe(a, s, d):
    z = 0
    w = 0
    q = 2
    e = []
    while q <= s:
        while z < a:
            if math.gcd(d[z], q) == 1:
                w = w + 1
            z = z + 1
        e.append(w)
        q = q + 1
        z = 0
        w = 0
    return e.index(max(e))
a,s = map(int, input().split())
d = list(map(int, input().split()))
print(2 + qwe(a,s,d))

Ограничение времени	2 секунды
Ограничение памяти	256Mb

Условие задачи:
На финал всероссийской командной олимпиады школьников по программированию (ВКОШП) приехали N команд. У каждой команды есть одно любимое число (у разных команд могут быть одинаковые любимые числа). Своё любимое число команда указывала при регистрации. Таким образом, жюри знает любимые числа всех команд. Жюри хочет выбрать некоторое своё любимое число и сообщить его на открытии олимпиады. Жюри считает, что команда будет удивлена, если окажется, что её любимое число и любимое число жюри взаимно-просты (то есть наибольший общий делитель этих двух чисел равен единице). Жюри хочет выбрать число таким образом, чтобы удивить как можно больше команд. Разумеется, жюри не хочет выбирать в качестве любимого числа единицу (это было бы слишком простым решением). С другой стороны, выбранное число не должно быть слишком большим, а именно — оно должно быть не больше X. Помогите жюри выбрать любимое число. Если существует несколько чисел, которые удивят наибольшее возможное количество команд, разрешается выбрать любое из них.

Формат ввода
В первой строке находятся два натуральных числа N и X — количество команд на олимпиаде и максимальное возможное значение любимого числа жюри (1 ⩽ N ⩽ 50 000, 1 < X ⩽ 109). Во второй строке даны N натуральных чисел — любимые числа команд, эти числа не превосходят 109.
Формат вывода
Вывести натуральное число, которое стоит выбрать жюри, чтобы удивить наибольшее количество команд. Выбранное число должно быть больше единицы и не превосходить X.