如何计算小于等于N的质数个数？

Question

我想编写一个程序来确定小于或等于 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 视为质数。我该如何修复这个程序？

Answer 1

您可以尝试这些改变：

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

• 一旦发现数字不是质数就打破内循环
• 使用Eratosthenes筛法

Answer 2

您可以试试下面的代码：

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”函数的列表中。我们还打印包含素数的列表的长度。