Задача foobar застряла на простых числах

Question

Я довольно застрял, теперь задание дается N найти положение N+4 символов в строке простых чисел. Например, строка простых чисел - 23571113...

Так:
n = 3 число = 71113

n = 0 число = 23571

n не может быть больше 10000

Вот мой код, который я старался изо всех сил, чтобы быть эффективным, но когда я пытаюсь выполнить тестовый случай 10000, он занимает слишком много времени, поэтому я думаю, что я провалил 4 из 10 тестовых случаев:

def answer(n):
    # your code here
    n = int(n)
    ID_len = 0
    input_limit = 10000  # adjustable limit for n
    y = 0 # Counter
    if n<= input_limit: #checks to make sure you're under the limit of 10000 for n
        try:
            while (ID_len < (n+5)):
                    y += 2
                    primes = [x for x in range(2, y + 1) if all(x%i for i in range(2,x))]
                    prime_str = ''.join(map(str,primes))
                    ID_len = len(prime_str)
            #print prime_str
            return  prime_str[n:n+5]
        except:
            pass
    else:
        print ("pick a number smaller than {0}".format(input_limit))

Что я могу сделать, чтобы сделать это более эффективным, или я просто задумываюсь над этой проблемой?

Answer 1

Немного поздно... Как вы заметили, вам не нужно вычислять primes на каждой итерации: просто переместите его из цикла и замените y адекватным значением в понимании списка. Но зачем продолжать вычисления? Если вы не ограничены комнатой, вы можете просто написать:

prime_str = "23579..." # 10000 chars here

Давайте предположим, что это не принято. В вашем коде есть как минимум два основных улучшения:

• вам не нужно строить полный prime_str;
• Вы можете закрепить primes поколение.

Первое улучшение:

N = n+5
s = " "*10 # a slice large enough
for prime in primes(): # a generator of primes (see below)
    prime_str = str(prime)
    N -= len(prime_str)
    # add the prime at the end of the slice, 
    # remove chars at the beginning to keep the size
    s = s[len(prime_str):] + prime_str        
    if N<0:
        return s[N-5:N] # return the correctp part of the slice.

Второе улучшение. Конечно, вы можете внедрить Сито Эратхостен, это может быть излишним здесь. Есть простая идея: если a = b * c, затем b >= sqrt(a) или же c >= sqrt(a), Следовательно, вы можете перестать искать делителя a когда вы достигнете sqrt(a):

def primes():
    return (x for x in itertools.count(2) if all(x % i != 0 for i in range(2, math.ceil(math.sqrt(x))+1)))

Answer 2

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