1

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

Will Ness
  • 70,110
  • 9
  • 98
  • 181
imRentable
  • 45
  • 5
  • I suppose no arrays also means no collections or anything that is essentially a collection? – kutschkem Oct 24 '14 at 09:24
  • 2
    Unless there is some variant of the sieve that I'm unaware of, this is not possible. The whole idea behind the sieve is to use an array (or list, or hashmap, or similar collection). Are you 100% sure you understood the assignment correctly? Are you really supposed to use a sieve, or any other prime finding algorithm without arrays? – tobias_k Oct 24 '14 at 09:49
  • yes im 100% sure because I and lots of my fellow students asked the professor about that matter and she replied we're only allowed to use the stuctures we already had in class. Which excludes all kinds of collections. And yes, it has to be the sieve, I wrote a code which does the same thing but isn't a sieve. I guess I'll submit this if i can't find a solution – imRentable Oct 24 '14 at 09:57
  • What structures did you have in class? In the worst case you could use two longs and bitwise operations to store values for N up to 128 ^_^ – Dawnkeeper Oct 24 '14 at 10:10
  • just primitive data types and control structures such as for, while, do-while, if, switch-case. – imRentable Oct 24 '14 at 10:33
  • @tobias_k *incremental* sieve replaces the contiguous array with a priority queue of primes' multiples, creating a "sliding" sieve (see it simulated [here](http://stackoverflow.com/a/11979874/849891)). But priority queue is a collection too. – Will Ness Oct 24 '14 at 22:20
  • @imRentable did you miss my comments? I show how it *can* be done, although for a relatively low top value limit. Up to a 100 it is very easily done. See the answer I linked to. – Will Ness Oct 25 '14 at 11:41
  • @Will Ness I have to admit that I didn't realise how the algorithm you suggested is actually a sieve of E. but I took another good look and now its clear to me. I guess one can't get closer to the sieve without arrays than the code you posted! thank you very much, I hope you don't mind if i'll use it for my homework? – imRentable Oct 25 '14 at 19:25

2 Answers2

1

The Sieve is about remembering the primes you found already. As far as I know there is no way to do this without arrays or lists and only with loops.
I checked some of the examples at RosettaCode at random and did not find one without an array and only loops.

If you add Classes and Methods as options you can come up with a recursive design:

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


}

This removes the array but uses Objects to store the Prime (each Sieve holds one prime)

Dawnkeeper
  • 2,844
  • 1
  • 25
  • 41
  • 1
    The sieve (of E.) is about remembering the *composites*, but that doesn't change the conclusion. Without any collections we're reduced to trial division or some other kind of primality testing -- which is *not* sieving. With the top limit sufficiently low [we *can* do it without arrays](http://stackoverflow.com/a/11979874/849891) by simulating a priority queue of multiples with just naked variables. But that's impractical for much above 100. – Will Ness Oct 24 '14 at 22:13
  • 1
    actually, to get to 10,000 we only need to keep track of multiples of 25 primes (the ones below 100). But that's *pushing it*, with 25 explicit variables. And the top limit can't be increased. – Will Ness Oct 24 '14 at 22:27
0

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.

Will Ness
  • 70,110
  • 9
  • 98
  • 181