python-3.x 如何计算小于或等于N的素数的数量?

zbdgwd5y  于 2023-03-20  发布在  Python
关注(0)|答案(3)|浏览(130)

我想写一个程序来确定小于或等于N(包含用户输入的变量)的素数的数量,这是我得到的结果:

N = int(input("Enter number: "))
count = 0
primes = []
for i in range(2, N+1):
    for j in range(2, int(i/2)+1):
        if (i % j) != 0:
            primes += [i]
            count += 1

print(count)
print(primes)

但是当我运行代码的时候,它不需要数字2和3是质数。我该怎么修复这个程序呢?

8mmmxcuj

8mmmxcuj1#

您可以尝试以下更改:

N = int(input("Enter number: "))
count = 0
primes = []
for i in range(2, N+1):
    is_prime = True
    for j in range(2, int(i/2)+1):
        if (i % j) == 0:
            is_prime = False
    if is_prime:
        primes += [i]
        count += 1
print(count)
print(primes)

要检查这个数是否是质数,你需要它来检查所有较小的数的余数是否都不等于0。
此外,primes += [i]应该在外部循环中,因为您希望每个数字最多计数一次。
请注意,此解决方案在效率方面远非最佳。一些改进可能是:

  • 仅将j迭代到math.sqrt(i)+1
  • 一旦发现数字不是质数,立即中断内部循环
  • 使用Sieve of Eratosthenes
mmvthczy

mmvthczy2#

您可以尝试以下代码:

primes = []
#Check if given number is prime
def num_is_prime(n):
    if n <= 1 :
        return False
  
    for i in range(2, n):
        if n % i == 0:
            return False
  
    return True
  
#Print prime number less than given number
def print_prime_num(n):
    for i in range(2, n + 1):
        if num_is_prime(i):
            primes.append(i)
            print(i)

    print("Number of prime numbers less than or equal to {} is {}.".format(n,len(primes)))

然后调用函数:

print_prime_num(YOUR_NUM)

num_is_prime函数在给定的数为质数时返回true,否则返回false。然后打印从2(第一个质数)到给定数的质数,并将它们添加到print_prime_num函数的列表中。我们还打印包含质数的列表的长度。

5uzkadbs

5uzkadbs3#

您的起点应该是编写一个有效的素数验证器。
例如:

primeset = {2, 3}

def isprime(n):
    if n in primeset:
        return True
    if n < 2 or n % 2 == 0 or n % 3 == 0:
        return False
    f = 5
    while f * f < n:
        if n % f == 0 or n % (f + 2) == 0:
            return False
        f += 6
    primeset.add(n)
    return True

那么,为了处理这种特殊情况:

N = int(input('Enter number: '))

primes = []

for p in range(2, N+1):
    if isprime(p):
        primes.append(p)

print(len(primes))
print(primes)

*注意:sympy 模块有一个 isprime() 函数,它将比这个函数快很多。可以通过更多代码进一步改进。2是唯一的偶数质数。因此,您可以检查它,然后(如果需要)从3开始以2为步长进行范围计算

相关问题