imRentable - 3 years ago 144

Java Question

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

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

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

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