Python 非素数生成器

Question

我需要帮助完成这项任务：给定一个整数 k，打印前 k 个非质数正整数，每个都换行。我尝试了几种方法，但似乎无法破解它。有没有办法找到这个解决方案？这是我的代码：def manipulate_generator(generator, n):    # Enter your code here      new_number = []      for x in range(1, n):          if n % x == 0:            new_number.append(x)      return new_number

Answer 1

首先，你的问题有几个问题。尽管“生成器”一词出现在您的标题中，并且在您的代码中出现了两次，但您的实际问题描述与 Python生成器没有任何关系。

其次，您的示例代码排序将k作为参数，n但此参数不应参与非素数计算本身。这只是对找到的数量的计数。看起来您从某个地方获取了试图解决不同问题的代码。

我喜欢@blhsing 的基于生成器的解决方案 (+1)，除了他们使用 aset来保存素数，因为 aset没有顺序。这是一个效率方面的问题，原因有两个。首先，在尝试大素数之前，我们不会尝试小素数，这将取消我们感兴趣范围内的更多数字的资格。所以我们可能会做一些不必要的划分。其次，如果某些素数大于我们正在测试的数字的平方根，则根本不应该使用它们。这些绝对是不必要的划分。

这是我的解决方案，它非常相似，但使用 a listof primes 来减少除法的数量。请注意，它是一个 Python生成器，尽管尚不清楚您所追求的与返回 a listof 复合材料的区别：

def composite_generator(k):

    number = 1

    if k > 0:

        yield number

        k -= 1

    number += 1

    primes = []

    while k:

        for divisor in primes:

            if divisor * divisor > number:

                primes.append(number)

                break

            if number % divisor == 0:

                yield number

                k -= 1

                break

        else:  # no break

            primes.append(number)  # for 2 and extremely large prime gaps

        number += 1

print(*composite_generator(20), sep='\n')

根据我编写的素数生成代码，我相信保留素数列表只会在这些相对较小的范围内将性能提高 10% 左右。在单独处理偶数之后使用奇数除数通常就足够了。

我认为@Prune 关于首先研究素数生成器的部分建议是个好主意。我会更进一步说先实现一个素数生成器，然后将其转换为复合生成器。

Answer 2

您可以使用集合来存储您已经找到的素数，并尝试将每个候选整数除以n已知素数，如果它是可整除的，则产生该数字；否则将该数字作为素数存储到集合中。继续递增，n直到产生k非素数。产生1第一个，因为它是唯一不能被素数整除的非素数：

def nonprimes(k):

    if k > 0:

        yield 1

    primes = set()

    n = 2

    while k > 1:

        for prime in primes:

            if n % prime == 0:

                yield n

                k -= 1

                break

        else:

            primes.add(n)

        n += 1

以便：

for n in nonprimes(10):

    print(n)

输出：

1

4

6

8

9

10

12

14

15

16

Answer 3

我最近也收到了同样的问题。它已经有一些现有的代码，我要做的就是完成“manipulate_generator”的代码。

现有代码：

def positive_integers_generator():

n = 1

while True:

    x = yield n

    if x is not None:

        n = x

    else:

        n += 1

k = int(input())

g = positive_integers_generator()

for _ in range(k):

    n = next(g)

    # print(n)

    manipulate_generator(g, n)

我的操作生成器代码和检查素数的支持函数：

from math import sqrt

# function to check if a given number is prime

def check_prime(n):

    is_prime = True

    for num in range(2, int(sqrt(n)) + 1):

        if n % num == 0:

            is_prime = False

            break

    return is_prime

def manipulate_generator(generator, n):

    # flag to ensure that manipulate_generator prints only one value per iteration

    printed = False

    

    while not printed:

        if n == 1:

            # printing 1 by default as its the first non-prime

            print(1)

            # update the flag to indicate value being printed and exit the while loop

            printed = True

        else:

            # check for the number to be prime

            is_prime = check_prime(n)

            

            # if its a non-prime number, print it

            if not is_prime:

                print(n)

                # update the flag to indicate value being printed and exit the while loop

                printed = True

            else:

                # if a prime number is encountered, generate the next number

                n = next(generator)

此代码在允许的范围内执行并获得所需的输出。