Prime Number Generation Puzzle (Edge Cases)

Question

Я решаю следующую проблему на сайте кодирования. Это не подходит для некоторых краевых случаев на тестах (скрытые тесты), но я не уверен, что это такое. Кто-нибудь видит какие-либо проблемы с этим?

Задача: Пусть A является строкой всех простых чисел, последовательно сжимаемых вместе (то есть 235711131719...). С учетом индекса n, верните строку из 5 цифр, где первая цифра находится в индексе n в A.

например. foo(0) => 23571 и foo(10) => 19232

Вот мой код:

def gen_primes():                                                  
    A = {}                                                   
    i = 2                                                    
    while True:                                                  
     if i not in A:                                                
      yield i                                                 
      A[i * i] = [i]                                               
     else:                                                   
      for p in A[i]:                                               
       A.setdefault(p + i, []).append(p)                                          
      del A[i]                                                 
     i += 1                                                  

def answer(n):                                                  

    counter = 0                                                  
    prime_string = ""                                                 

    for p in gen_primes():                                               
     if (counter >= n): 
      prime_string += str(p)                                             
     counter += len(str(p))                                              
     if len(prime_string) >= 5:                                             
      break                                                  

    return prime_string[:5]  

Answer 1

Я думаю, что это может нарушить для простых чисел с более чем одной цифрой:

Давайте предположим, что мы достигли простых чисел с тремя цифрами, например 103. Counter составляет 10 и n является 11 (это просто пример, я не знаю, если это точное созвездие будет повернуть вверх)

Тогда мы должны были бы использовать тыс e цифры «03» из «103». Но так как counter меньше, чем n, пробег целиком пропущен. Программа будет продолжена с 107.

Вы можете исправить это, полностью удалив counter: всегда добавляйте штрихи к строке, выходите из цикла, если длина строки равна n+5 или больше.

EDIT:

Я проверил ваш код: пример answer(5) и answer(6). С вашим кодом оба вызова приводят к «13171». Вторая цифра «11» пропущена.

С помощью этого кода:

def answer(n):                                                  

    counter = 0                                                  
    prime_string = ""                                                 

    for p in gen_primes(): 
     prime_string += str(p)                                              
     if len(prime_string) >= n+5:                                             
      break                                                  

    return prime_string[n:n+5] 

Они приводят к

11317 # answer(5) 
13171 # answer(6) 

Answer 2

Вот мой ответ; он похож на @lhk, но использует скользящее окно вместо того, чтобы хранить всю строку:

phil@haydn ~ $ python 
Python 2.7.5+ (default, Sep 17 2013, 15:31:50) 
[GCC 4.8.1] on linux2 
Type "help", "copyright", "credits" or "license" for more information. 
>>> def primegen(): # http://stackoverflow.com/a/20660551 
...  yield 2; yield 3   # prime (!) the pump 
...  ps = primegen()   # sieving primes 
...  p = next(ps) and next(ps) # first sieving prime 
...  D, q, c = {}, p*p, p  # initialize 
...  def add(x, s):   # insert multiple/stride 
...   while x in D: x += s # find unused multiple 
...   D[x] = s    # save multiple/stride 
...  while True:    # infinite list 
...   c += 2    # next odd candidate 
...   if c in D:   # c is composite 
...    s = D.pop(c)  # fetch stride 
...    add(c+s, s)  # add next multiple 
...   elif c < q: yield c # c is prime; yield it 
...   else: # (c == q)  # add sqrt(c) to sieve 
...    add(c+p+p, p+p) # insert in sieve 
...    p = next(ps)  # next sieving prime 
...    q = p * p   # ... and its square 
... 
>>> def primeSubstr(n): # nth character in concatenated primes 
...  ps = primegen()   # sequence of prime numbers 
...  i, s = 0, ''    # current index, sliding window 
...  while True:    # do ... until i == n 
...   if len(s) < 5:  # sliding window too small 
...    s+=str(next(ps)) # add next prime to window 
...   elif i < n:   # not yet to target index 
...    i, s = i+1, s[1:] # slide window to right 
...   else: return s[:5] # return desired substring 
... 
>>> primeSubstr(0) 
'23571' 
>>> primeSubstr(5) 
'11317' 
>>> primeSubstr(10) 
'19232' 
>>> primeSubstr(15) 
'93137' 
>>> primeSubstr(20) 
'41434' 
>>> primeSubstr(1000) 
'98719' 
>>> CTRL-D 

Я буду обсуждать эту проблему завтра в my blog.

Answer 3

это выглядит как работа для itertools, как об этом

>>> from sympy import sieve 
>>> from itertools import islice, chain 
>>> def primeSubStr(n): 
     primes=iter(sieve) 
     next(primes) 
     return "".join(islice(chain.from_iterable(map(str,primes)), n, n+5)) 

>>> primeSubStr(0) 
'23571' 
>>> primeSubStr(10) 
'19232' 
>>> primeSubStr(5) 
'11317' 
>>> primeSubStr(15) 
'93137' 
>>> primeSubStr(20) 
'41434' 
>>> primeSubStr(1000) 
'98719' 
>>> primeSubStr(2000) 
'98940' 
>>> 

Для простоты я использую sympy.sieve, чтобы получить простые числа, но любой способ получения простых чисел будет работать нормально, как и те, here, например.

Теперь самое интересное, карта достаточно очевидно, тем, что мы получаем поток "2", "3", "5", "7", "11", "13", ... "101", "103", ... затем chain.from_iterable что поток расстроенным в потоке одиночных цифр "2", "3", "5", "7", "1","1", "1","3", ... "1","0","1", "1","0","3", ... и, наконец, с islice мы принимаем участие, мы хотим и присоединиться к ней для окончательного результата