代码之家 › 专栏 › 技术社区 › Dominic

查找列表中素数的比例,代码错误(Python)

error-correction python

0

Dominic · 技术社区 · 6 月前

如上所述,我知道我的方法不起作用,所以我会重做,但我也想知道为什么我得到了错误的答案。

len_limit = 6 # for generating primes. I've adjusted this limit based on how far I get up to
limit = 10 ** len_limit 
primes2 = [True] * (limit + 1)
primes2[0] = primes2[1] =  False
for i in range (2,int(limit ** 0.5) + 1):
    for n in range(2, int(limit / i) + 1):
        primes2 [i*n] = False
primes = []
for i in range(len(primes2)):
    if primes2[i] == True:
        primes.append(i)

def make_square(side_length): # making all the numbers into a list
    a,b = 0,0
    nums = [1]
    square_size = side_length
    for n in range(2,square_size): 
        nums.append(4 * n ** 2 - 10 * n + 7)    # NE
        nums.append((2*n - 1) ** 2)             # SE
        nums.append(4 * n ** 2 - 8 * n + 5)     # NW
        nums.append(4 * n ** 2 - 6 * n + 3)     # SW
    nums.sort()
    return nums

def fraction_prime(side_length):
    nums = make_square(side_length)
    a,b = 0,0
    for num in nums:
        if num in primes:
            a += 1
            b += 1
        else:
            b += 1
    return (a/b)

i = 3
while True:
    i += 1
    fraction_prime(i)
    side_length = 2 * i - 3
    # print(fraction_prime(i),side_length,i) # optional, just to check that it was working
    if fraction_prime(i) <= 0.40: # not the number needed in the question, just to see if it works
        print(fraction_prime(i),side_length,i)
    if fraction_prime(i) < 0.40:
        break

2 回复 | 直到 6 月前

1

2

Apichet Janya 6 月前

你的黄金餐桌只高达 1,000,000 ,但螺旋中的对角线值要大得多(数亿)。
任何超过你限制的东西都会被自动视为非素数,所以你的比率下降得太早了,这就是为什么你得到的是631而不是26000。

if num in primes 列表上的值是O(n)O(n。既然你已经 primes2 ,使用 primes2[num] 相反。

要得到正确答案,你必须

生成素数,直到 最大对角线值 ,或
跳过大筛子,用简单的素数检查来测试每个对角线值。


def is_prime(n: int) -> bool:
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2
    return True


prime_count = 0   
diag_count = 1    
layer = 0 


TARGET_NUM = 1
TARGET_DEN = 10

while True:
    layer += 1
    side_length = 2 * layer + 1  
    high = side_length * side_length  
    step = side_length - 1      


    for k in range(4):
        val = high - k * step
        if is_prime(val):
            prime_count += 1

    diag_count += 4


    # prime_count / diag_count < 1/10  <=>  10 * prime_count < diag_count
    if TARGET_DEN * prime_count < TARGET_NUM * diag_count:
        print("=== Result ===")
        print(f"Layer        : {layer}")
        print(f"Side length  : {side_length}")
        print(f"Prime count  : {prime_count}")
        print(f"Diag count   : {diag_count}")
        print(f"Prime ratio  : {prime_count / diag_count:.12f}")
        break

print("Done.")

2

0

Martin Brown 6 月前

这是其中一个谜题,用一个显式的方阵来做这件事的明显方法——其中大多数不是素数——是不可能慢的。

你只需要考虑和测试出现在正方形四条对角线中的三条上的数字,它们可以通过简单的差分算法(或公式)快速生成,适用于远离正方形中心的任何位置。差分法通常更快。

对角线序列及其第一和第二差异如下:

1   3    13    31    57    91     
  2   10    18    26    34
    8     8     8     8     8

1   5    17    37    65   101
  4   12    20    28    36
    8     8     8     8

1   7    21    43    73    111
  6   14    22    30    38
    8     8     8     8     

1   9    25    49    81    121
  8   16    24    32    40
    8     8     8     8

这四条对角线中的最后一条可以忽略,因为它们都是奇数的平方。生成规则是添加一个偶数,每次递增8。

生成需要检查的对角线数字的代码片段:

  n3 = 1
  delta_n3 = 2
  n5 = 1
  delta_n5 = 4
  n7 = 1
  delta_n7 = 6
  
  for s in range(side_length)
      n3 += delta_n3
      n5 += delta_n5
      n7 += delta_n7
      delta_n3 += 8
      delta_n5 += 8
      delta_n7 += 8

稍微狡猾一点,你也可以从n3和n7流中删除所有除以3的值。更难的是,你可以从n5流中除以5。

NB is不需要考虑除以2,因为它不会出现在这个问题中。