imRentable imRentable - 3 years ago 144
Java Question

Sieve of Eratosthenes without arrays?

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.

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.

my code until now:

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


-> 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! :)

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. :(

Answer Source

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.

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download