嵇爾的吐槽

#没事画轮子的嵇尔不定期的(W)碎(E)碎(B)念(B)和(L)吐(O)槽(G)

Problem 58 Spiral primes 2017-04-18 13:50:00

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

             
37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18 5 4 3 12 29
40 19 6 1 2 11 28
41 20 7 8 9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

import math


def is_Prime(number):
    if number < 2:
        return False
    for x in range(2, int(math.sqrt(number)) + 1):
        if number % x == 0:
            return False
    return True


i = 0
pre = 0
count = 0

while True:
    if i is 0:
        count += 1
    else:
        size = i * 2 - 1
        top_left = (i * 2)**2 + 1
        top_right = top_left - 2 * i
        bottom_left = top_left + 2 * i
        #bottom_right = ((i * 2) + 1)**2
        count += 4
        if is_Prime(top_left):
            pre += 1
        if is_Prime(top_right):
            pre += 1
        if is_Prime(bottom_left):
            pre += 1
    print i * 2 + 1,
    print pre, count,
    rate = float(pre) / float(count)
    print rate
    if i > 0 and rate < 0.1:
        break
    i += 1

[Finished in 16.5s]

去print

[Finished in 12.7s]

Prime list使用的场景也需要斟酌

评论共