Putting prime numbers into an array

[Rujal Duale]

Hi there,
Is there a better way (simplier way) of writing this method?

     /*Method is supposed to put all prime numbers in an array */
    public static void listPrimes(int maxNum) {
        for (int i = 1; i < maxNum; i++) {
            boolean isprime = true;
            for (int j = 2; j < i; j++) {
                if (i > 1 && j < i && i % j == 0) {
                    isprime = false;
                    break;
                }
            }
 
            if (isprime) {
                array[counter] = i;
                counter++;
            } else
                System.out.print(""); //what should I do when it ain't prime?
        }
    }

thanks a lot
[ December 16, 2005: Message edited by: Jim Yingst ]

[Paul Clapham]

what should I do when it ain't prime?

Nothing.

However you should probably add some code to break out of the loop after you fill in the last entry in the array.

[Rujal Duale]

Ok Paul, array over-flow is taken care.

[Minh Huy Nguyen]

think about the BigO, this way is kind of slow with a big number.
A simpler way is:

public class Prime {
    static int[] array = new int[23000];
    static int counter = 0;
 
    public static void listPrime(int max) {
        int[] flag = new int[max];
 
        for (int i = 2; i < max; i++) {
            if (flag[i] == 0) {
                array[counter++] = i;
                int limit = max / i;
                for (int j = 2; j < limit; j++) {
                    flag[i * j] = 1;
                }
            }
        }
        for (int i = 0; i < counter; i++) {
            System.out.print(array[i] + " ");
            if (i % 10 == 0)
                System.out.println();
        }
    }
 

    public static void main(String[] args) {
        listPrime(27000);
    }
}

[ December 16, 2005: Message edited by: Jim Yingst ]

[Ravisekhar Kovuru]

for(int j=2; j<i; j++){
    if( i>1 && j<i && i%j==0){
        isprime = false;
        break;
    }

<hr></blockquote>
You don't need to loop thru until j < i .
It is enough to loop thru until j < (int) Math.sqrt(i) .
This is based on the mathematical fact that 'if a number is not divisible (with 0 reminder) by any number between 2 and its square root, then it won't be divisible by any number beyond its square root either'

This change will cause a very drastic cut down in execution time.
For example to check if 971 is a prime or not, with j < i the loop will be executed 969 times, where as with j < (int) Math.sqrt(i) the loop will only be executed 29 times.

[ December 16, 2005: Message edited by: Jim Yingst ]
[ December 16, 2005: Message edited by: Ravisekhar Kovuru ]

[Jim Yingst]

I added [code] tags to the above posts to improve readability. Please use these in the future.

[Ravisekhar]: It is enough to loop thru until j < (int) Math.sqrt(i) .

Good idea, but slightly off. If i is 9 for example, Math.sqrt(9) is 3. But the loop will only test j = 2, not j = 3, because of the requirement that j < 3. This needs slight modification. I'd also point out that the sqrt() method need only be called once for each i, before the j loop begins. It's needlessly slow to evaluate sqrt() many times inside the j loop since it's the same for each i.

Another thing to think about - do you really need to test devision by all the numbers from 2 to sqrt(i)? For example, do you need to divide by 4? If the number were divisible by 4, it also would have been divisible by 2, which was tested earlier. Similarly 6 could be skipped, and 8, 9, 10, 12... In fact you could skip every non-prime number here. Is there some way to do that? (Hint: in the original problem, you're building a list of prime numbers. Can we use that?)

[Ravisekhar Kovuru]

Yes Jim, you are right,
thanks for pointing out..
So I think this modification would be ok:

  
boolean isprime = true;
[B]int root = (int) Math.sqrt(i);[/B]
for (int j = 2; [B]j <= root[/B]; j++) {              
if (i > 1 && j < i && i % j == 0) {   
  isprime = false;
  break;  
}
}

And I am not sure about how to skip every non-prime number.
Can some one help in this regard.
[ December 16, 2005: Message edited by: Ravisekhar Kovuru ]

[Junilu Lacar]

Look around the web for "Sieve of Erastosthenes" -- that is what the algorithm is called.

BTW, you want to use "code" tags to preserve indentation, not "quote"
[ December 16, 2005: Message edited by: Junilu Lacar ]

[Jim Yingst]

[Ravisekhar]: And I am not sure about how to skip every non-prime number.

Well, skipping every non-prime number would be the same as using every prime number (from 2 to sqrt(i)). The original poster had a variable named "array" that was basically a list of prime numbers. By looping through that array, you loop through a list of prime numbers. If that's still confusing, I recommend just working on the earlier algorithm and making sure it's working correctly.

[Rujal Duale]

Thanks to all for your help. The programme is working fine and much faster after incorporating Math.sqrt(i). Appreciate it.
[ December 18, 2005: Message edited by: Rujal Duale ]