1

Дан список чисел который я ввожу с экрана, нужно найти наибольшее количество подряд идущих простых чисел в порядке возрастания (отрицательные тоже считаются) и найти их, если этих рядов несколько, считать тот ряд у которого сумма этих простых чисел больше.

Вот сам код

from itertools import groupby

nums = map(int, input().split())


def isPrime(n):
    if n < 0:
        n = -n
    elif n == 0 or n == 1:
        return False
    for a in range(2, (n//2)+1):
        if n % a == 0:
            return False
    return True

primes = [list(g) for k,g in groupby(map(int,nums),key=isPrime) if k]

res = max(filter(lambda x: x==sorted(x),primes),key=sum,default=[])

print(len(res), sum(res))

Вот пример ввода и вывода:

Ввод:
20 -7 -7 -2 0 1 3 5 5 10

Вывод:
3 13

Тут посчиталось что сумма ряда 3 5 5 больше чем -7 -7 -2, из за этого взяли 3 5 5

Ещё один пример
Ввод:
5 -2 -2 10 8

Вывод:
2 -4

вроде бы на вот эти вводы код работает, но когда ввожу
7 2 7 4 4 10 12 7 -2 -4 7
мне почему разбивает на эти массивы:
[7, 2, 7], [7, -2], [7] a должен был на эти [7], [2, 7], [7], [-2], [7]

Смысл в том, что он ищет среди этих массивов самый длинный а потом считает их сумму, в этом случае, это массив [2, 7]
Не могу понять, почему иногда код работает, а иногда нет.
Может выдать мне, когда ввожу, например:
2 2 2 2 2 7 5
он разбивает на массив:
[2, 2, 2, 2, 2, 7, 5]
а не на массивы
[2, 2, 2, 2, 2, 7], [5]

4
  • я не люблю включать "зануда моде", но по определению "Просто́е число́ — натуральное (целое положительное) число, имеющее ровно два различных натуральных делителя — единицу и самого себя". Это я к тому, что отрицательных простых чисел не бывает. Ну или называются они "простыми числами со знаком минус".
    – S.H.
    3 окт 2021 в 9:24
  • 1
    Я что-то не вижу нигде в коде никаких проверок на возрастание. Вот оно и группирует просто последовательности простых чисел.
    – GrAnd
    3 окт 2021 в 9:53
  • можете какую то наводку дать, через что мне лучше пойти, чтобы находило простые числа по возрастанию?
    – Khimer
    3 окт 2021 в 17:06
  • Хорошая задача. Интересно было бы отыскать изящное решение. Какое-нибудь без циклов с хранимым состоянием. 3 окт 2021 в 19:53

1 ответ 1

1

Вы сами указали что разбиение на группы слишком грубое. Совсем простого решения я не нашёл. Можно сделать аннотации - каждому числу из списка приписать номер группы в которое оно входит. Одновременно с аннотированием из списка удаляются не простые.

k - ключ/номер группы. Ключ увеличивается если очередное число не простое или простое но меньше предыдущего. Наружу выдаются пары (ключ, число) только для простых чисел (это не оптимизация!).

def group_primes(seq):
    k = 0
    prev_n = 0
    for n in seq:
        prime = is_prime(abs(n))
        if not prime or prev_n > n:
            k += 1
        if prime:
            yield k, n
        prev_n = n
[2, 2, 2, 2, 2, 7, 5] ->
[(0, 2), (0, 2), (0, 2), (0, 2), (0, 2), (0, 7), (1, 5)]

[7, 2, 7, 4, 4, 10, 12, 7, -2, -4, 7] ->
[(0, 7), (1, 2), (1, 7), (6, 7), (7, -2), (8, 7)]

Из аннотированной последовательности groupby с соответствующим ключом правильно соберёт группы, которые нужно будет очистить удалив ключи и оставив числа.

import itertools
import math


def is_prime(n):
    assert n >= 0
    if n < 2:
        return False
    return all(n % d != 0 for d in range(2, math.floor(math.sqrt(n)) + 1))


def group_primes(seq):
    k = 0
    prev_n = 0
    for n in seq:
        prime = is_prime(abs(n))
        if not prime or prev_n > n:
            k += 1
        if prime:
            yield k, n
        prev_n = n


def main():
    # все числа
    a = map(int, input().split())

    # простые числа, аннотированные ключами
    b = group_primes(a)

    # простые числа, собранные в группы
    c = (
        # из группы оставляем только числа без ключей
        tuple(n for _, n in g)
        # группировка только по ключу, значение игнорируется
        for k, g in itertools.groupby(b, key=lambda v: v[0])
    )

    # переделываем группы в пары (длинна, сумма)
    d = ((len(g), sum(g)) for g in c)

    # выбираем самую длинную группу
    # если таких несколько, то с самой большой суммой
    e = max(d, default=(0, 0))

    print(*e)


main()

Группа 3 5 5 обходит -7 -7 -2:

$ echo "20 -7 -7 -2 0 1 3 5 5 10" | python ascending-primes.py 
3 13

Здесь наибольшая по сумме группа 2 7:

$ echo "7 2 7 4 4 10 12 7 -2 -4 7" | python ascending-primes.py
2 9

Переход через ноль в группе -3 -2 2 3:

$ echo "-3 -2 2 3" | python ascending-primes.py 
4 0

Ни одного простого:

$ echo "0 1 4 6 8 9 10 12" | python ascending-primes.py 
0 0

Длина группы важнее суммы (и снова переход через ноль):

$ echo "7 2 5 5 5 15 10 -7 -7 -5 -2 -2 5" | python ascending-primes.py 
6 -18
8
  • спасибо большое за решение, немного изменил функцию is_prime, в моем случае отрицательное по модулю число, тоже простое. И из-за этого, он ряд из отрицательных чисел тоже считать должен, например в ситуации : Ввод: 7 2 5 5 5 15 10 -7 -7 -5 -2 -2 5 и вывод: 4 17 , а должно быть 5 -23. И еще в таких ситуациях где вообще нет ряда из простых чисел, что выводит 0 0, например: ввод: 0 0 1 8 4 вывод: 0 0. В моем ситуации 1 не простое число. Из за того что изменил функцию is_prime на свой, мне выводит ошибку что max() is an empty sequence, не могу до конца понять как работает itertools.
    – Khimer
    3 окт 2021 в 20:16
  • В коде вызывается is_prime(abs()). Должен получаться тот же результат что и у вас. Единица - не простое число и у меня и у вас. 3 окт 2021 в 20:26
  • Вызов max дополнил параметром default=() для обработки случая когда простых в списке нет совсем. 3 окт 2021 в 20:31
  • Про ваш пример: какую группу выбрать 4 17 или 5 -23? В вопросе сказано "максимальная сумма" и 17 > -23, следовательно ответ 4 17. Что я делаю не так? 3 окт 2021 в 20:35
  • Ещё пример из вопроса: 20 -7 -7 -2 0 1 3 5 5 10 -> 3 13 не 3 -16. 3 окт 2021 в 20:36

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.