Циркулярное простое проект Эйлера № 35 - PullRequest
Новая
       17

Циркулярное простое проект Эйлера № 35

1 голос
/ 13 апреля 2019

Это проблема, которую я пытаюсь решить.

Число 197 называется круговым простым, потому что все вращения цифр: 197, 971 и 719 сами просты.

Существует тринадцать таких простых чисел ниже 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79 и 97.

Сколькокруговые простые числа меньше одного миллиона?

Это моя попытка.Сначала я поместил все простые числа ниже 1000000 в список, называемый простыми числами, затем рассчитал все их возможные перестановки и сохранил эти перестановки в списке.Затем я проверил, являются ли эти перестановки простыми или нет. 

import math
def isPrime(num):
    flag = 1
    root = int(math.sqrt(num) + 1)
    for i in range (2,root+1):
        if num%i == 0:
            flag = 0
            break
        else:
            flag = 1
    if flag == 1:
        return True
    else:
        return False

primes = [#list of all primes below 1000000]

def permutations(word):
    if len(word) == 1:
        return [word]
    char = word[0]
    perms = permutations(word[1:])
    result = []
    for perm in perms:
        for i in range (len(perm)+1):
            result.append(perm[i:] + char + perm[:i])
    return result

count = 0
for i in primes:
    to_be_tested = permutations(str(i))
    count_to_be_fulfilled = len(to_be_tested)
    new_count = 0
    for j in to_be_tested:
        if isPrime(int(j)):
            new_count += 1
    if new_count == count_to_be_fulfilled:
        count += 1
print(count)

Я получил ответ 22 и согласно Project Euler это неправильно.Я не знаю ответа, так как хочу решить это самостоятельно и не хочу обманывать.Пожалуйста, скажите мне, что я делаю не так.

1 Ответ

0 голосов
/ 14 апреля 2019

Решение

Я не опубликую полное решение, потому что из Project Euler о разделе:

Я так много узнал, решая проблему XXX, так что можно опубликовать мою решение в другом месте?

Похоже, что вы ответили самостоятельно вопрос. Ничего подобного "Ага!" момент, когда ты наконец, победить проблему, над которой вы работали в течение некоторого времени. Часто из лучших побуждений мы хотим поделиться нашими понимание, чтобы другие тоже могли насладиться этим моментом. К сожалению, однако, это не будет иметь место для ваших читателей. Реальное обучение является активным процесс и видеть, как это делается, еще далеко от Богоявление открытия. Пожалуйста, не отрицайте других, что у вас так богато себя ценил.

Однако я дам вам несколько советов.

Структуры данных

Как я уже упоминал в комментарии, использование наборов значительно улучшит производительность вашей программы, потому что доступ к данным в них действительно быстрый (вы можете узнать почему, прибегая к помощи метода, называемого hashing , если ты не знаешь об этом). Точно, производительность со списками будет O(N), тогда как с сетами она будет около O(1).

Вращения против перестановок

В постановке задачи вам необходимо рассчитать повороты числа. Как отметил @ottomeister, вы должны действительно проверить, выполняет ли ваша программа то, что ожидает от нее постановка задачи. В настоящее время вызов permutations("197") вернет следующий список - ['791', '917', '179', '971', '719', '197'] - тогда как проблема ожидает, что результат будет ['197', '971', '719']. Вместо создания перестановок вы должны вычислить вращений , что можно найти, например, перемещая каждую цифру влево (с переносом), пока не будет возвращено начальное число (может сделать такой рекурсивный алгоритм, если он вам действительно нравится).

Первичная проверка

В настоящее время вы проверяете, является ли каждое число простым, выполняя цикл, который проверяет, делится ли число N на все, вплоть до sqrt(N). Как вы заметили, это довольно медленно для многих чисел, и есть лучшие способы проверить, является ли число простым. В вашем сценарии идеальным решением будет просто сделать N in primes, потому что вы уже сгенерировали простые числа, которые, если вы используете наборы вместо списков, будут O(1). Кроме того, вы можете взглянуть на тесты простоты (особенно эвристические и вероятностные тесты)

Наконец

Обычно я рекомендую тестировать ваше собственное решение, прежде всего, вы могли легко заметить, что ваша функция permutations не соответствует ожидаемым результатам постановки задачи. Я предлагаю разбить вещи дальше на более мелкие функции, например, у вас может быть функция rotations(number), аналогичная вашей permutations, может быть, функция is_circular(number), которая проверяет, соответствует ли данное число проблемным требованиям, и функция count_circular(upper_bound), которая вычисляет и считает круглые числа. Если вы также прокомментируете все по ходу дела, это значительно упростит отладку, и вы сможете на ходу подтвердить, что все работает, как и ожидалось:)

...