Задача foobar застряла на простых числах - PullRequest
Новая
       30

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

0 голосов
/ 27 апреля 2018

Я застрял, теперь задание по заданному 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))

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

Ответы [ 2 ]

0 голосов
/ 16 мая 2018

Немного поздно ... Как вы заметили, вам не нужно вычислять 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.

Второе улучшение. Конечно, вы можете реализовать сито Erathostenes, это может быть излишним здесь. Идея проста: если 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)))
0 голосов
/ 27 апреля 2018

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

...