没有阵列的Eratosthenes筛? [英] Sieve of Eratosthenes without arrays?

问题描述

我必须为"eratosthenes筛子"算法编写一个Java代码，以在控制台上打印出高达给定最大值的素数，但不允许使用数组.我们的教授告诉我们，仅在循环的帮助下是可行的.

I have to write a java code for the 'sieve of eratosthenes' algorithm to print out primes up to a given max value on the console but I'm not allowed to use arrays. Our professor told us it is possible to do only with the help of loops.

因此，我对此思考了很多，并在Google上搜索了很多，却找不到答案.我认为这根本不可能，因为您已经存储了某些数字已经被划掉的信息.

So I thought a lot and googled a lot about this topic and couldn't find an answer. I dont think it's possible at all because you have store the information which digits are already crossed out somewhere.

直到现在我的代码:

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;
        }
    }
}

->因此，我不允许对数字进行"i％mark！= 0"命令，该数字是我已经打印的数字的倍数，但是我应该如何在没有数组的情况下弄清楚这一点?删除索引上的数字?

-> So, i'm not allowed to do the "i % mark != 0" command with numbers which are multiples of the numbers i already printed but how am i supposed to make that clear without an array where i can delete numbers on indexes?

但是，如果有解决方案，我很高兴有人可以与我分享！ :)

BUT if there is a solution I would be glad if someone could share it with me! :)

该解决方案可以使用其他编程语言，如果可能的话，我可以自己将其翻译为Java.

The solution can be in other programming languages, i can translate it to java myself if its possible.

在此先感谢您，并致以最诚挚的问候

Thank you in advance and best regards

更新:非常感谢大家，我非常感谢您的帮助，但是我认为使用基本结构无法做到.我见过的所有使用基本结构打印出质数的算法都不是橡皮擦的筛子. :(

Update: Thank you very much all of you, i really appreciate your help but I don't think it can be done with the basic structures. All the algorithms i have seen yet which print out primes by using basic structures are no sieve of eratosthenes. :(

推荐答案

我正在收回我之前说的话.这就是Haskell中没有数组的筛子":

I'm taking back what I said earlier. Here it is, the "sieve" without arrays, in Haskell:

sieve limit = [n | n <- [2..limit], null [i | i <- [2..n-1], j <- [0,i..n], j==n]]

这是一个健忘筛子，并且非常效率很低.仅使用加法和整数比较.其中的列表理解可以用命令式语言重新编码为循环.或者换句话说，它 移动 的计数就像筛子一样，但没有标记任何内容，因此不使用任何数组.

It is a forgetful sieve, and it is very very inefficient. Uses only additions, and integer comparisons. The list comprehensions in it can be re-coded as loops, in an imperative language. Or to put it differently, it moves counts like a sieve would, but without marking anything, and thus uses no arrays.

当然，您是否将其视为真"筛子取决于您对筛子的定义.这个不断地创造和放弃他们.或者您可以说它重新实现了 rem 函数.实际上，这是同一句话，并且解释了为什么当 reuse (通常通过数组)成为可能时，筛子突然变得如此高效的原因.

Of course whether you'd consider it a "true" sieve or not depends on what is your definition of a sieve. This one constantly recreates and abandons them. Or you could say it reimplements the rem function. Which is the same thing to say, actually, and goes to the essence of why the sieve suddenly becomes so efficient when reuse - via arrays usually - becomes possible.

这篇关于没有阵列的Eratosthenes筛?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！