Как я могу улучшить свой код на проблему Эйлера 7 - PullRequest
Новая
       15

Как я могу улучшить свой код на проблему Эйлера 7

1 голос
/ 11 мая 2019

Я начал изучать Python, и после некоторого базового изучения я начал заниматься проблемой ЭйлераМне удалось сделать 7, но сборка занимает много времени.Кто-нибудь может мне помочь?

Это единственный код, который я написал 

def prime(n):
    count = 0
    if n <= 1:
        print("Number is neither prime nor composite")
    if n == 2:
        print("Number is prime")
    if n > 2:
        for i in range(2, n//2 + 1):
            if n % i == 0:
                count += 1
            else:
                count += 0
    if count == 0:
        return True
    else: 
        return False


b = 10001
a = []
i = 2
while len(a) < b:
    if prime(i):
        a.append(i)
        i += 1
    else:
        i += 1
print(a[-1])

Ответы [ 3 ]

1 голос
/ 11 мая 2019

Нет необходимости искать все факторы числа. Как только вы найдете фактор, число, очевидно, не простое, и вы можете немедленно вернуть False.

EDIT:
Как отметил Федерико Доменикони в комментариях, нет необходимости повторять до половины n. Итерации до его квадратного корня будет достаточно: 

if n > 2:
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False

    # No factors found, n is a prime:
    return True
0 голосов
/ 17 мая 2019

Если вы работаете с проблемами Project Euler, тогда неплохо бы иметь собственное Сито Эратосфена .Это может вычислить простое число очень быстро, намного быстрее, чем пробная факторизация, метод, который вы используете в настоящее время.Вы найдете его полезным для ряда их проблем.

Тогда решение Euler 7 становится следующим:

  1. Оцените размер 10,001-го простого числа, используя Теорема о простых числах .

  2. Запустите сито Эратосфена до предела, начиная с шага 1, и немного выше для безопасности.

  3. Посчитайте через выход из вашего сита, чтобы найти 10,001-е простое число.

0 голосов
/ 12 мая 2019

И если вы действительно хотите свести этот тип решения к минимуму: 

def is_prime(n):
    factors = range(2, int(math.sqrt(n)) + 1)
    return (n > 1 and all(n % f for f in factors))

Один неожиданный элемент пустяков, который я мог бы знать однажды и забыть.Почему функция возвращает True для n = 2? 

factors # range(2, 1 + 1)
        # range(2, 2)
        # Which is an empty range.
        # Or in more concrete form: an empty list.

n > 1   # True
all([]) # Hmmmmm?
        #
        # Are all of the items in an empty collection true?
        #
        # If every tree falls in the forest at once, but no one hears them,
        # does it make a sonic boom?
        #
        # Contrary to Billy Preston -- and microeconomists world wide --
        # can you really get something from nothing?
        #
        # Python says YES. I'm sure smart mathematics do too, but
        # I would be curious to hear the reasoning.

Я думаю, у StackOverflow есть ответ на мой вопрос.И у логиков есть имя для этой ситуации: " пустая правда - это утверждение, которое утверждает, что все члены пустого набора имеют определенное свойство."

...