0

Тут есть уже похожий вопрос. Но всё-таки... Делал т.з для одной компании. Получил отказ, "ответ неверный". Помогите разобраться что не так. Охота ведь осознать ошибку если она есть.

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

Мой ответ: (9966006699, 99979, 99681)

def get_palindrom():

    for i in range(99999, 90001, -1):
        if i / 2 != 0 and i / 3 != 0 and i / 5 != 0 and i / 7 != 0:
            for j in range(99999, 90001, -1):
                if j / 2 != 0 and j / 3 != 0 and j / 5 != 0 and j / 7 != 0:
                    prod = i * j
                    if str(prod) == str(prod)[::-1]:
                        return prod, i, j
    print(get_palindrom())
9
  • а почему именно эти ограничения выставлены? Вдруг одно больше число можно сделать, а другое меньше.
    – pavel
    8 ноя 2017 в 18:07
  • "Результат произведения двух пятизначных чисел" число должно быть максимальным. Собственно поэтому и выставил такой диапазон. Если с нуля идти к большему очень на долго этот процесс зависает, начал с конца. Ещё пробовал набивать список результатами н-ного количества итераций (ставил 10 и 20) и максимальный ответ был тот-же
    – TheBob
    8 ноя 2017 в 18:10
  • ещё раз... откуда взялось ограничение СНИЗУ?
    – pavel
    8 ноя 2017 в 18:12
  • Всё, сорри, не тот вариант выложил. Это уже кода игрался и варианты искал...ещё раз сорри
    – TheBob
    8 ноя 2017 в 18:13
  • 3
    Что ещё смешнее 99681 делится на 3
    – Alexey Ten
    8 ноя 2017 в 18:48

4 ответа 4

2

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

Во-вторых, такого числа может просто не оказаться среди множителей из выбранного вами диапазона(90001...99999) - один из множителей может быть, например, 77813.

1

Так как ограничений на время нет, то можно в лоб все произведения простых чисел с 5 цифрами перебрать:

#!/usr/bin/env python3
from itertools import combinations


def ispalindrome(n):
    digits = str(n)
    return digits == digits[::-1]


def primes_upto(limit): 
    """Sieve of Eratosthenes."""
    prime = [True] * limit
    for n in range(2, limit):
        if prime[n]:
            yield n  # prime
            for composite in range(n * n, limit, n):
                prime[composite] = False


primes5digit = [p for p in primes_upto(10**5) if p > 10**4]
print(*max((p * q, p, q) for p, q in combinations(primes5digit, 2)
           if ispalindrome(p * q)))

Подождать десятки секунд и результат:

999949999 30109 33211
0

Кажется разобрался... В проверке на то является ли число простым поставил не тот знак...должно быть "%" вместо "/" ну и соответственно ответ другой получился...судя по всему оно...

1
  • проверка остатка деления (% p) где p 2,3,5,7 не достаточно, чтобы гарантировать что число простое. К примеру, 99979 не является простым.
    – jfs
    10 ноя 2017 в 6:02
0

Как Вам такой подход:

from sympy import sieve
from itertools import combinations_with_replacement

def max_palindrome(prime_numbers):
    prime_numbers_list_unique_combinations = combinations_with_replacement(prime_numbers, 2)
    list_palindromes = ((i * j, i, j) for i, j in prime_numbers_list_unique_combinations if \
                        str(i * j) == str(i * j)[::-1])
    result = max(list_palindromes)
    return "The max palindrome with product numbers {1} and {2} is: {0}".format(result[0], \
                                                                                 result[1], \
                                                                                 result[2])

print max_palindrome((i for i in sieve.primerange(9999*3, 99999/3)))
# The max palindrome with product numbers 30109 and 33211 is: 999949999

requirements:

mpmath==1.0.0
sympy==1.1.1

Ваш ответ

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

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