Проект Эйлера Задача 35: подсчет круговых простых чисел ниже 1 миллиона

Задача 35 Эйлера Эйлера :

  

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

     

Сколько круговых чисел есть ниже миллиона?

import itertools
import math
import time

prime_list = []
#num = 14
count = 0
limit = 100000
time.clock()

def get_primes(n):
    numbers = set(range(n, 1, -1))
    #primes = []
    while numbers:
        p = numbers.pop()
        prime_list.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    #return primes

get_primes(limit)

print "Done", time.clock()

for r in xrange(2,limit):
    #b = 1
    if r in prime_list:
        #print r,count
        num = str(r)
        if (all(int(num[i:]+num[:i]) in prime_list for i in xrange(len(num)))):
            count += 1
print count,time.clock()

Я генерирую все возможные простые числа с другой функцией, и он дает мне выход в 60-80 мс для limit = 1000000

Тем не менее, цикл занимает около 19 секунд для нахождения среднего значения счетчика при пределе = 100000

11 голосов | спросил Unique 24 42016vEurope/Moscow11bEurope/MoscowThu, 24 Nov 2016 12:30:26 +0300 2016, 12:30:26

4 ответа


5

Для prime_list требуется быстрый тест для in prime_list: вот что означает set. Использование списка дает линейные тесты времени, тогда как набор должен быть почти постоянным.

С другой стороны, set не гарантирует порядок итерации, поэтому я думаю, что get_primes, вероятно, глючит.

ответил Peter Taylor 24 42016vEurope/Moscow11bEurope/MoscowThu, 24 Nov 2016 12:37:30 +0300 2016, 12:37:30
9

Что касается простых чисел выше 10. Если они простые, и все их вращения должны быть целыми числами, то каждая цифра должна быть в наборе 1, 3, 7 и 9. Итак, для всех 2 цифр чисел, \ $ 4 ^ 2 \ $, для всех 3 цифр, \ $ 4 ^ 3 \ $, до 6. Это точно 5456 номеров для проверки, что очень мало, по сравнению с 1 миллионом. Теперь у нас есть все возможные числа и только те.

Кроме того, вы играете с числами с максимальным значением 1 миллион. Вам также нужно проверить , если число является простым. Для этого вам нужно всего лишь генерировать простые числа до 1000 и проверять, является ли один из кандидатов делимым на любое из этих простых чисел. Есть 168 простых чисел до 1000. Таким образом, вы можете хранить их в массиве. Это быстрее, чем всегда генерация простых чисел снова и снова.

Это уже улучшит ваше время на действительно большой фактор.

ответил Olivier Grégoire 24 42016vEurope/Moscow11bEurope/MoscowThu, 24 Nov 2016 16:54:42 +0300 2016, 16:54:42
7

Разделите свой код на более мелкие, многоразовые, проверяемые, документированные части

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

import time

def get_primes(n):
    """Get list of prime number from 2 to n included."""
    prime_list = []
    numbers = set(range(n, 1, -1))
    while numbers:
        p = numbers.pop()
        prime_list.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    return prime_list

def euler35(limit = 100000):
    count = 0
    prime_list = get_primes(limit)
    for r in xrange(2,limit):
        if r in prime_list:
            num = str(r)
            if (all(int(num[i:]+num[:i]) in prime_list for i in xrange(len(num)))):
                count += 1
    return count

def test_get_primes():
    assert get_primes(1) == []
    assert get_primes(2) == [2]
    assert get_primes(7) == [2, 3, 5, 7]
    assert get_primes(8) == [2, 3, 5, 7]
    assert get_primes(9) == [2, 3, 5, 7]
    assert get_primes(10) == [2, 3, 5, 7]
    assert get_primes(11) == [2, 3, 5, 7, 11]

def test_euler35():
    assert euler35(100) == 13
    assert euler35() == 43

test_get_primes()

time.clock()
test_euler35()
print(time.clock())

Оптимизация: использование правильной структуры данных для правильной задачи

Как упоминалось в другом ответе , используя set вместо list должно привести к явным улучшениям производительности.

Вам просто нужно обновить:

prime_list = get_primes(limit)

в

prime_set = set(get_primes(limit))

Упростите код

Вы можете избавиться от if r in prime_set, итерации напрямую prime_set. Также вы можете избавиться от лишних круглых скобок:

def euler35(limit = 100000):
    count = 0
    prime_set = set(get_primes(limit))
    for r in prime_set:
        num = str(r)
        if all(int(num[i:]+num[:i]) in prime_set for i in xrange(len(num))):
            count += 1
    return count

Различные алгоритмы первичной генерации

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

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

def sieve(lim):
    """Computes the sieve of Eratosthenes for values up to lim included."""
    primes = [True] * (lim + 1)
    primes[0] = primes[1] = False
    for i in range(2, int(math.sqrt(lim)) + 1):
        if primes[i]:
            for j in range(i * i, lim + 1, i):
                primes[j] = False
    return primes

def primes_up_to(lim):
    """Uses a sieve to return primes up to lim included."""
    return (i for i, p in enumerate(sieve(lim)) if p)

def euler35(limit = 1000000):
    count = 0
    prime_set = set(primes_up_to(limit))
    for r in prime_set:
        num = str(r)
        perms = [int(num[i:]+num[:i]) for i in xrange(len(num))]
        if all(p in prime_set for p in perms):
            count += 1
    return count

Разная стратегия

Обычно Project Euler - это нечто большее, чем просто реализация прямого решения: может быть хорошей идеей найти решение, которое будет работать для еще больших поисковых пространств. Вы найдете такую ​​стратегию в этом другом обзоре кода .

Вот код, который я написал (аргумент работает несколько иначе, но вы получите его), и соответствующие модульные тесты, которые вы могли бы использовать, чтобы проверить, что мой код работает ~ в 10 раз быстрее :

def is_prime(n):
    """Checks if a number is prime."""
    if n < 2:
        return False
    return all(n % i for i in range(2, int(math.sqrt(n)) + 1))

def euler35_bis(nb_dig_max=6):
    # permutations of 2 digits or more must contain only 1, 3, 7, 9
    count = 4  # counting 2, 3, 5 and 7
    final_numbers = {'1', '3', '7', '9'}
    for l in range(2, nb_dig_max + 1):
        for p in itertools.product(final_numbers, repeat=l):
            p_int = int(''.join(p))
            perm = {int(''.join(p[i:] + p[:i])) for i in range(len(p))}
            if p_int == min(perm) and all(is_prime(n) for n in perm):
                count += len(perm)
    return count

def test_euler35():
    assert euler35(100) == 13
    assert euler35(100000) == 43
    assert euler35() == 55

def test_euler35_bis():
    assert euler35_bis(2) == 13
    assert euler35_bis(5) == 43
    assert euler35_bis() == 55

test_get_primes()

time.clock()
test_euler35()
# test_euler35_bis()
print(time.clock())
ответил Josay 24 42016vEurope/Moscow11bEurope/MoscowThu, 24 Nov 2016 14:31:18 +0300 2016, 14:31:18
2

Вы должны написать функцию is_even (N), чтобы проверить, есть ли в any четная цифра (0,2,4,6,8) в любом месте цифр основного номера. Если есть, верните False, даже не потрудитесь вращаться, потому что в какой-то момент четное число придет к концу и сделает число не круговым простым.

Это должно значительно снизить нагрузку на проверку.

ответил Tirtha 7 PMpFri, 07 Apr 2017 21:51:47 +030051Friday 2017, 21:51:47

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132