Eratosthenes Sieve-找到划掉数字的顺序

Question

第一次出租。我说这不是家庭作业：）在Eratostennes Sieve中，从1到给定的数字k，我想找到并返回划掉给定数字n的顺序，而不使用列表、元组、集合和字典（或此类数据结构）

我想出了下面的代码，它将向我显示从2到k的总合数。但是我无法提出我的主要问题的一般想法。

k = int (input())
n = int (input())
order = 0 
for i in range(2,n+1):
   for j in range(2,i): 
     if i%j ==0: 
         order += 1  
         break
print (order)

举个例子，如果你注意到数字1-10的代码，你会看到10在9后面被划掉了。而事实并非如此。如果你能帮我修改这段代码，我将不胜感激，因为我已经在这上面思考了7个星期了

Answer 1

埃拉托斯特尼筛（Sieve of Eratosthennes）从4的倍数2（=2^2）开始，然后从9的倍数3（=3^2），以此类推，穿过素数。你可以用你目前所发现的来决定下一个要使用的素数。

这给出了删除顺序:4，6，8，10，...9, 12, 15, 18, ...25, 30, 35, 40, ...49, 56, 63, 70, ...121, 132, 143, ...

Answer 2

这执行您的问题描述所说的操作。我们保留一组已经划掉的合数。对于范围内的每个数字，如果它不是一个已知的复合，那么我们“划掉”该数字的所有倍数，这些倍数尚未在合成集中。我们在划掉复合材料时打印它们。

k = int(input())
n = int(input())
comps = set()
order = 0 
for i in range(2,n+1):
    if i in comps:
        continue
    for j in range(i+i,n,i):
        if j not in comps:
            comps.add(j)
            print(j)
            if j == k:
                order = len(comps)
print()
print(order)