Оптимизация Python с большими числами

Question

Я хочу напечатать все простые числа с 7 последовательными 7 с менее 10000000000. Я получал MemoryError при использовании range(), потому что сгенерированный массив не мог быть сохранен, поэтому я изменил цикл на цикл while.

Однако программа действительно медленная. Печать первого найденного номера занимает более минуты.

import math 

def is_prime(n): 
    if n % 2 == 0 and n > 2: 
     return False 
    i = 3 
    while i < math.sqrt(n) + 1: 
    #for i in range(3, int(math.sqrt(n)) + 1, 2): 
     if n % i == 0: 
      return False 
     i += 2 
    return True 

def is_super_happy(n): 
    count = 0 
    while n != 0: 
     if n%10 == 7: 
      count += 1 
      if count == 7: 
       return True 
     else: 
      count = 0 
     n /= 10 
    return count == 7 

i = 7777777 
while i < 10e10: 
#for i in range(7777777, int(10e10)): 
    if is_super_happy(i) and is_prime(i): 
     print i 
    i += 1 

Я ничего не могу сделать, чтобы это ускорилось, и я хочу, чтобы это было очень быстро.

Любые идеи, советы?

Answer 1

Два предложения:

• Генерировать 7, 8 и 9-х цифр, тем меньше, чем 10e10, содержащие 7777777 непосредственно (а не проверять каждый и каждое число в свою очередь), а затем проверить их. Есть относительно небольшое число таких чисел.

  Например, вот способ, чтобы создать список всех таких чисел, конечных с «7777777»: [int(str(x)+'7777777') for x in xrange(100)]

• Рассмотрим, используя вероятностный тест для проверки простоты (например, Miller-Rabin). Это говорит вам, является ли число x простым с очень высоким уровнем вероятности и намного быстрее, чем проверка потенциально тысяч чисел, меньших, чем x для делимости.

Answer 2

Ваш текущий алгоритм очень расточительный: is_prime проверяет каждое число от 1 до sqrt(n) на каждой итерации, тогда как он должен проверять только простые простые числа.

Измените алгоритм так, что он реализует http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

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

Answer 3

Я нахожу 250 простых чисел примерно за четверть секунды, я не хочу давать свой код, потому что ваш вопрос выглядит как домашнее задание.

Методы:

• первых, найти все простые числа ниже 100 000 (это SQRT (ваш максимальное число)), используя сито.
• is_prime() необходимо только проверить, не делит ли какой-либо из этих простых чисел номер
• Есть только 4000 таких чисел; рассмотрите цифры от 000 до 999. Их можно комбинировать с 7777777 четырьмя способами; 123 становится 7777777123, 1777777723, 1277777773 и 1237777777. Создайте их, проверьте их против примитивности, сделайте.
• Используйте строки (int("12" + "7777777" + "3")) или просто математика (12 * 100000000 + 7777777 * 10 + 3) для генерации чисел