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 += 1print(*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)输出：146891012141516

Answer 3

我最近也收到了同样的问题。它已经有一些现有的代码，我要做的就是完成“manipulate_generator”的代码。现有代码：def positive_integers_generator():n = 1while True:    x = yield n    if x is not None:        n = x    else:        n += 1k = 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 primedef 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_primedef 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)此代码在允许的范围内执行并获得所需的输出。