1. Python / Говнокод #10349

    −104

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    36. 36
    37. 37
    38. 38
    39. 39
    40. 40
    41. 41
    42. 42
    43. 43
    44. 44
    45. 45
    46. 46
    47. 47
    48. 48
    49. 49
    50. 50
    51. 51
    52. 52
    53. 53
    54. 54
    55. 55
    56. 56
    57. 57
    58. 58
    59. 59
    60. 60
    61. 61
    62. 62
    63. 63
    64. 64
    65. 65
    66. 66
    SIEVE_SIZE = 4096

def primes():
    s = [False] * 2 + [True] * (SIEVE_SIZE - 2)
    primel = []

    # Bootstrap sieve
    for i in xrange(SIEVE_SIZE):
        if s[i]:
            yield i
            primel.append(i)
            j = i
            while j < SIEVE_SIZE:
                s[j] = False
                j += i

    # Main loop
    seg = SIEVE_SIZE
    while True:
        s = [True] * SIEVE_SIZE
        for p in primel:
            j = (seg / p) * p - seg
            if j < 0:
                j += p
            while j < SIEVE_SIZE:
                s[j] = False
                j += p

        # Yield next set of primes
        for p in map(lambda x: x[0], filter(lambda x: x[1],
                enumerate(s, seg))):
            yield p
            primel.append(p)

        seg += SIEVE_SIZE

pg = iter(primes())
test_primes = []

p = next(pg)
while p < 1000:
    test_primes.append(p)
    p = next(pg)

ps = set(test_primes)
ps.add(p)
pm = p

def is_prime(n):
    global pm
    while pm < n:
        pm = next(pg)
        ps.add(pm)
    return n in ps

def get_formula_length(a, b):
    n = 1
    t = lambda n: n * n + a * n + b

    while t(n) > 0 and is_prime(t(n)):
        n += 1

    return n

print max((get_formula_length(a, b), a * b) for b in test_primes
    for a in xrange(-999, 1000))[1]

    http://projecteuler.net/problem=27
    http://projecteuler.net/thread=27;page=6

    >Phooey, scrolling through the comments I can see my code could benefit from quite some improvements. That being said, I use a sliding sieve of Eratosthenes to generate an "infinite" list of primes. This is then used in combination with brute force to find the right solution.

    Запостил: TheHamstertamer, 23 Мая 2012

    Комментарии (17) RSS

    • ava bormand 23.05.2012 13:40 # +3

      is_prime брутален: вместо того, чтобы проверить делимость на простые, меньшие чем sqrt(n) мы генерим все простые числа до n, и смотрим, что n среди них :)

      Хотя для таких маленьких n и большого числа проверок - может и правда быстрее.
      Ответить

      • ava unu-foja 23.05.2012 15:02 # 0

        Написано же, что решетом эратосфена решили просеять.
        Ответить

        • ava unu-foja 23.05.2012 15:30 # +1

          Впрочем, напрямую вполне приемлемо (python3):
          from math import sqrt, floor
from functools import lru_cache

@lru_cache(maxsize=None)
def is_prime(n):
    n = abs(n)
    for i in range(2, floor(sqrt(n))):
        if n % i is 0: return False
    return True

n_max = 40
bs = list(filter(is_prime, range(-999,1000)))

for a in range(-999,1000):
    for b in bs:
        n = 1
        while is_prime(n * n + a * n + b): n += 1
        if n > n_max:
            (n_max, a_max, b_max) = (n, a, b)

print (a_max * b_max)
          Ответить

    • ava bormand 23.05.2012 14:06 # 0

      Так сойдет? 
      primes = 2 : filter isPrime [3..]
isPrime x = check primes where
    check (p:ps) | p*p > x        = True
                 | x `mod` p == 0 = False
                 | otherwise      = check ps

primes1 = takeWhile (<1000) primes
primes2 = primes1 ++ map (\x -> -x) primes1

primeLength a b = length $ takeWhile isPrime $ map (\n -> n*n+a*n+b) [0..]

main = do
    let (_, a, b) = maximum [(primeLength a b, a, b) | a <- [-999..999], b <- primes2]
    print (a*b)

      Учетки от PE под рукой не было, ответ проверить нечем :(
      Ответить

      • ava bormand 23.05.2012 14:21 # 0

        Да, баг, надо вот так:
        primeLength a b = length $ takeWhile isPrime $ takeWhile (>0) $ map (\n -> n*n+a*n+b) [0..]


        И primes2 втопку, все равно b не может быть отрицательным.
        Ответить

    • ava TarasB 23.05.2012 16:48 # 0

      j = (seg / p) * p - seg
      if j < 0:
      j += p

      В питоне нету оператора остатка от деления?
      Ответить

      • ava bormand 23.05.2012 17:01 # +1

        Есть.
        Ответить

      • ava TheHamstertamer 23.05.2012 18:04 # +2

        % же.
        Ответить

        • ava TarasB 23.05.2012 20:42 # 0

          Спасибо, Кэп.
          Вы оба так отвечаете, будто то ли не поняли мой тонкий намёк, то ли я неверно понял, что эти три строки возвращают остаток от деления.
          Ответить

          • ava Lure Of Chaos 23.05.2012 20:50 # 0

            таки необязательно оО http://ru.wikipedia.org/wiki/Деление_с_остатком
            Ответить

            • ava TarasB 23.05.2012 21:30 # 0

              Почему? Про интеллоарифметику не будем, тут всё положительное.
              Ответить

          • ava bormand 24.05.2012 06:21 # 0

            Эти три строки возвращают не остаток. Пусть p=3, тогда 10->2 11->1 12->0. А эту формулу уже так просто не записать:
            j = p - seg % p
if j == p:
    j = 0
            Ответить

    • ava Lure Of Chaos 23.05.2012 20:39 # 0

      > global pm
      пиххипишнег писал, не иначе.
      Ответить

    • ava wvxvw 24.05.2012 13:07 # 0

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

      • ava bormand 24.05.2012 13:28 # 0

        А он не вычисляет их по-новой, он только добавляет недостающие в set.
        Ответить

    Добавить комментарий