没有阵列的厄拉多塞之筛？

Question

我必须为'sieve of eratosthenes'算法编写一个java代码，以便在控制台上打印出给定最大值的素数，但我不被允许使用数组。我们的教授告诉我们，只有在循环的帮助下才能做到这一点。

所以我想了很多，在谷歌上搜索了很多关于这个话题的信息，但都找不到答案。我认为这根本不可能，因为你已经把那些数字已经被划掉的信息存储在某个地方了。

我的代码到现在为止：

public static void main(String[] args) {
    int n = 100;
    int mark = 2;

    System.out.print("Primes from 1 to "+n+": 2, ");
    for (int i = 2; i <= n; i++) {
        if(i % mark != 0){
            System.out.print(i+", ");
            mark = i;
        }
    }
}

-

但是如果有一个解决方案，如果有人能和我分享，我会很高兴！:)

这个解决方案可以用其他编程语言编写，如果可能的话，我可以自己把它翻译成java。

提前感谢您和最好的问候

更新：非常感谢大家，我真的很感激你的帮助，但我认为基本结构无法完成。我见过的所有通过使用基本结构打印出素数的算法都不是埃拉托斯特尼的筛子。:(

Answer 1

我收回了我之前说过的话。这是哈斯克尔中没有数组的“筛子”：

筛限=[n|n

这是一个健忘的筛子，效率非常低。只使用加法和整数比较。其中的列表推导可以用命令式语言重新编码为循环。或者换句话说，它像筛子一样移动计数，但不标记任何东西，因此不使用数组。

当然，你是否认为它是一个“真正的”筛子取决于你对筛子的定义是什么。这个不断地重新创造和抛弃它们。或者你可以说它重新实现了rem函数。实际上，这是同样的事情，并且涉及到为什么当重用（通常通过数组） 成为可能时，筛子突然变得如此高效。

Answer 2

筛子是关于记住你已经找到的素数。据我所知，没有数组或列表，只有循环，就没有办法做到这一点。
我随机检查了RosettaCode的一些示例，没有找到一个没有数组和只有循环的示例。

如果您将类和方法添加为选项，您可以提出递归设计：

public class Sieve
{

    private int current;
    private int max;
    private Sieve   parent;

    public Sieve(int current, int max, Sieve parent )
    {
        this.current = current;
        this.max = max;
        this.parent = parent;
    }

    public static void main(String[] args)
    {
        int n = 100;

        System.out.print("Primes from 1 to " + n + ":\n");

        printPrimes(n);
    }

    private static void printPrimes(int i)
    {
        new Sieve(2,i,null).start();    
    }

    private void start()
    {
        if(current <2 || max <2)
        {
            return;
        }

        if(this.current > max)
        {
            parent.print();
            return;
        }

        for(int i = this.current+1;current<=max+1;i++)
        {
            if(this.testPrime(i))
            {
                new Sieve(i,this.max,this).start();
                return;
            }
        }
    }

    private boolean testPrime(int i)
    {
        if(i%this.current != 0)
        {
            if(this.parent == null)
            {
                return true;
            }
            else
            {
                return this.parent.testPrime(i);
            }
        }
        return false;
    }

    private void print()
    {
        if(this.parent != null)
        {
            this.parent.print();
        }

        System.out.print(" "+this.current);
    }


}

这将删除数组，但使用对象来存储素数（每个筛子包含一个素数）