Проверьте, содержит ли список чередующиеся простые числа и совершенные квадраты

Question

Я только начинаю программировать на Python.У меня была проблема с проверкой, содержит ли данный список чередующуюся последовательность простых чисел и совершенных квадратов.Список может начинаться с простого или идеального квадрата.Я придумал решение, но оно неэффективно, так как генерирует нежелательные списки.Возможно ли это с более эффективным кодом Python?

Сначала я создаю функции для генерации списка простых чисел, а также совершенных квадратов до максимального значения списка тестирования.Функции squaretest() и primecheck():

---

def squaretest(num):
    sqlist=[]
    i=1
    while i**2 <= num:
        sqlist.append(i**2) 
        i+=1
    return sqlist

def primecheck(num):
    primelist=[]
    for i in range(2,num + 1):
            for p in range(2,i):
                if (i % p) == 0:
                    break
            else:
                primelist.append(i)
    return primelist

---

Затем я делю данный список на списки элементов четного индекса и нечетного индекса и проверяю все их элементы на соответствие primelist и squarelist:

def primesquare(l):
    if len(l)==1:
        primelist = primecheck(l[0])
        sqlist = squaretest(l[0])
        return (l[0] in primelist) or (l[0] in sqlist)
    else:
        ol=[]
        el=[]
        for i in range(0,len(l),2):
            ol.append(l[i])
        for p in range (1, len(l),2):
            el.append(l[p])
        primelist = primecheck(max(l))
        sqlist = squaretest (max(l))
        return((all(x in primelist for x in el)) == True and (all(y in sqlist for y in ol)) == True) or ((all(x in primelist for x in ol)) == True and (all(y in sqlist for y in el)) == True)

---

Работает.Любые предложения будут действительно полезны.

Answer 1

Я придумала решение, но оно неэффективно, поскольку оно генерирует нежелательные списки.

Если предположить, что нежелательные списки - это два списка, представляющие четные и нечетные элементы, то мы можем исправитьтот.(Устранение списка простых и квадратов - это целая «другая проблема». Ниже моя переделка вашего кода - мы не создаем дополнительные списки, а скорее с парой многократно используемых диапазонов , которые являются объектами, которые производятцелочисленные последовательности по мере необходимости, но не хранящиеся в памяти.

Ваш any() дизайн эффективен в том, что аргументы являются выражениями генератора, а не списками, которые вычисляются по мере необходимости.Как только в массиве обнаруживается недостаток, все останавливается и возвращает False - ему не нужно обрабатывать остальное:

def squares(number):
    return {x * x for x in range(int(number ** 0.5) + 1)}

def primes(number):
    prime_set = set()

    for i in range(2, number + 1):
        for p in range(2, int(i ** 0.5) + 1):
            if (i % p) == 0:
                break
        else:  # no break
            prime_set.add(i)

    return prime_set

def primesquare(array):
    if not array:
        return True  # define as the problem demands

    length, maximum = len(array), max(array)

    odd, even = range(0, length, 2), range(1, length, 2)

    prime_set, square_set = primes(maximum), squares(maximum)

    return all(array[i] in prime_set for i in even) and all(array[i] in square_set for i in odd) or all(array[i] in prime_set for i in odd) and all(array[i] in square_set for i in even)

Я восхищаюсь решением @ AndreySemakin на основе множеств (+1), и используйте наборы выше, но его решение генерирует те же списки, которые вы хотите исключить (только в форме наборов).

Answer 2

Я придумал это решение:

def primesquare(lst):

    # checking if the first element is either perfect square or a prime
    if not lst or (not checksquare(lst[0]) and not checkprime(lst[0])):
        return False

    length = len(lst)

    if length == 1:
        return True

    if checksquare(lst[0]):
        # if first element is square then make s(quare)=2 and p(rime)=1
        s, p = 2, 1
    else:
        # if first element is prime then make s=1 and p=2
        s, p = 1, 2

    # running perfect square loop from s to len-1 with gap of 2 and checking condition
    for i in range(s, length, 2):
        if not checksquare(lst[i]):
            return False

    # running prime loop from p to len-1 with gap of 2
    for i in range(p, length, 2):
        if not checkprime(lst[i]):
            return False

    return True

def checksquare(n):  # function to check perfect square

    if n < 0:
        return False

    if 0 <= n <= 1:
        return True

    for i in range(int(n ** 0.5) + 1):
        if i * i == n:
            return True

    return False

def checkprime(n):  # function to check prime

    if n < 2:
        return False

    if n % 2 == 0:
        return n == 2

    for i in range(3, int(n ** 0.5) + 1, 2):
        if n % i == 0:
            return False

    return True

Answer 3

Вы можете использовать устанавливает , чтобы проверить, все ли члены списка находятся в другом списке.

def primesquare(l):
    if len(l) == 0:
        return True

    primelist = set(primecheck(max(l)))
    sqlist = set(squaretest(max(l)))

    ol = set(l[::2])
    el = set(l[1::2])

    odds_are_primes = ol.issubset(primelist)
    odds_are_squares = ol.issubset(sqlist)
    evens_are_primes = el.issubset(primelist)
    evens_are_squares = el.issubset(sqlist)

    return (odds_are_primes and evens_are_squares) or (odds_are_squares and evens_are_primes)