告诉我们 100 到 10000 之间的哪个 100 周期有最多素数的程序

Question

我想写一个程序来告诉我们在 100 到 10000 之间的 100 中的哪个周期（即 100 到 200 或 200 到 300 等等的哪个百类）有最多的质数。我不知道如何解决这个问题并对数百个进行分类，我知道如何判断两点之间有多少个质数，但我如何在计算每个百之间的质数时迭代 100 到 10000。谢谢你的时间。

Answer 1

我写了一个非常简单的程序来完成你的要求，我们遍历 100-199、200-299 等范围。对于每个范围，我们计算素数的数量。每次我们找到比我们保存的最大值更多的素数时 - 我们更改该最大值并保存我们发现的范围。

代码：

import math
def is_prime(x):
    #for num in range(2, int(x**0.5) + 1):
    for num in range(2, int(math.sqrt(x)) + 1):
        if x % num == 0:
            return False
    return True

def find_maximum_range_with_primes():
    max_range = None
    max_counter = 0

    # 10 ranges total: 100-200, 200-300, ...
    for j in range(1, 10):
        counter = 0

        # count primes in range
        for i in range(100*j ,100*(j+1)):
            
            if is_prime(i):
                counter += 1
                #print(i) 

        # if current range has more primes than the maximum found
        # set maximum to hole the counter, and save the range
        
        if counter > max_counter:
            max_counter = counter
            max_range = (100*j, 100*(j+1))
    return max_range

print(find_maximum_range_with_primes())

现在，这段代码没有优化，所以请注意有办法让它变得更好，但对于你的要求，我相信它会达到目的。

Answer 2

一旦你有了在一个范围内查找素数的函数，你就可以遍历范围：

import math

def is_prime(n):
    m = int(math.sqrt(n))
    i = 2
    while i <= m:
        if n%i == 0:
            return False
        i += 1
    return True


def primes(end_number:int, start_number:int=2):
    return [i for i in range(max(2, start_number), end_number+1) if is_prime(i)]

n_primes = 0
best_interval = None
for x in range(100, 10100, 100):  # looping through ranges happens here
    pn = primes(x, x-100)
    if len(pn) > n_primes:
        n_primes = len(pn)
        best_interval = (x-100, x)
    print("{:6d}-{:6d} ---> {:4d}".format(x-100, x, len(pn)))

print("Best interval is: {:15}".format(str(best_interval)))

Answer 3

这不是您的教师想要的，但了解 sympy 很有用，即使只是为了检查您的答案。

寻找素数最少的区间更有趣，你可以通过将 max 函数更改为 min （并将打印中的“最多”更改为“最少”） ).

import sympy

intervals = [(len(list(sympy.primerange(a, a + 100))), (a, a + 100)) for a in range(100, 10000, 100)]
winner = max(intervals, key=lambda t: t[0])
print(f'The interval with the most primes is {winner[1]} with {winner[0]} primes')

告诉我们 100 到 10000 之间的哪个 100 周期有最多素数的程序

Program to tell us which period of 100s between 100 to 10000 has the most prime numbers

python

primes