Java Code puzzle

[Shaan Shar]

Algorithm for finding Prime Numbers?

[Shaan Shar]

No Solution so far!!!

[Gabriel Claramunt]

Hmmm.... I saw *exactly* the same problem in an internal coding contest from some consulting company... coincidence? ;)
Have you given any though to the possible solution? I think if you find a mapping from coordinates to primes, you're done!

[Brian Legg]

Think about this from a logical point of view...

What makes a number prime? Only divisible by itself and 1.
How can I tell if a number is only divisible by itself and 1?

This could be done in many ways.... have you started on it at all?

[Paul Yule]

I actually seem to remember this originally being a different problem. There were prime numbers in a circularish pattern and you had to be able to get the prime based on coordinants. Either way if you have anything on either of the problems you posted I'd love to see your thoughts up to this point.

[Brian Legg]

Ok Paul, just for you

Here is my approach:

public ArrayList<int> findPrimes(ArrayList<int> numbers) {
	ArrayList<int> allPrimeNumbers = new ArrayList<int>();
	
	for(prime : numbers) {
		boolean isPrime = true;
		for(int divisor = 2; divisor <= (prime/10); divisor++) {
			if((prime % divisor) == 0) {
				isPrime = false;
				break;
			}
		}
		if(isPrime == true) {
			allPrimeNumbers.add(prime);
		}
	}
	return allPrimeNumbers;
}

I'm at work and I haven't done any Java in a while so I can't test this for accuracy or syntax errors. The basic concept is that you loop through each of the numbers in your array and see if any of them are divisible by a number between 2 and 10% of our number we are testing. Why 10%? Because after you go through 10% of the possible numbers you will start repeating the lower ones you already checked, like this:

100 is divisible by:
1 x 100
2 x 50
4 x 25
5 x 20
10 x 10

You can see that if we check any numbers higher than 10 the amount of times it can go into 100 will be less than 10, and we already checked all those so we can stop when we reach 10% of any number. If a divisor goes into our prime evenly then it's not prime. We set the flag to false and exit to our next test subject. Each one that passes the test is added to a new array and eventually returned containing just prime numbers.

Let me know if my logic is off or if the code doesn't work.

[Brian Legg]

Now that I have thought about it some more I think this could be even more efficient. I think it will work as is but could be done differently to return the answer much faster. 10% is guaranteed for higher numbers but doesn't work for lower ones.... also 10% is a lot more numbers than is neccassary to check on higher numbers.

Now I need to go figure out the formula for where the divisors meet on a given number.

For anyone testing my code as it is now, only pass in large numbers :P

[Brian Legg]

Bah, I got it.... the numbers always meet at the square root of the number.

sq 100 = 10
sq 273529 = 523

I'll update my code later... I don't know the java sytax for square root. ;)

[Gabriel Claramunt]

Finding primes is a well known problem without an easy solution.
If the number is not too big, you can use Eratosthenes Sieve.

[Maris Orbidans]

Brian, your code isn't correct. It wont even compile because primitives cannot be used as parametric types.

[Maris Orbidans]

I fixed your code

public ArrayList<Integer> findPrimes(List<Integer> numbers) {
        ArrayList<Integer> allPrimeNumbers = new ArrayList<Integer>();

        for(int prime : numbers) {
            boolean isPrime = true;
            for(int divisor = 2; divisor <= Math.sqrt(prime); divisor++) {
                if((prime % divisor) == 0) {
                    isPrime = false;
                    break;
               }
           }
           if(isPrime == true) {
               allPrimeNumbers.add(prime);
           }
       }
       return allPrimeNumbers;
   }  

[Brian Legg]

Thanks, it's been a while since I've used any Java

So.... does it work?

[Gabriel Claramunt]

This was my take at generating the sieve... I guess I overcomplicated a little

private static List<Integer> primesList(int max){
		boolean[] sieve=new boolean[max+1];
		for (int i=2; i<=max; i++){
			sieve[i]=true;
		}
		int prime=2;
		boolean done=false;
		while (!done){
			for (int i=prime+prime;i<=max;i=i+prime){
				sieve[i]=false ;
			}
			for (int j=prime+1; j<=max ; j++ ){
				if (sieve[j]){
					prime=j;
					break;
				}
				done=j==max;
			}
			
		}
		List<Integer> primes=new ArrayList<Integer>();
		for (int i = 0; i < sieve.length; i++) {
			if (sieve[i]){
				primes.add(i);
			}
		}
		return primes;
	}

[Brian Legg]

No point using 3 loops when 1 will do I always say

Nice job though!

[Gabriel Claramunt]

Brian Legg wrote:No point using 3 loops when 1 will do I always say

Nice job though!

Yep, 3 loops is too much.. I'm not convinced of starting with 2 either, but anyway... I wrote the code in a hurry too
Let me rewrite as an opportunity to get minimalistic on Java

[Garrett Rowe]

Gabriel Claramunt wrote:I guess I overcomplicated a little

No this is over complicating it. Here is a sieve inspired by this paper. (Look ma' no arrays!)

   public static List<Integer> primes(int max) {
      Map<Integer, List><Integer>> primeMap = new HashMap<Integer, List><Integer>>();
      List<Integer> primes = new ArrayList<Integer>();

      for (int i = 2; i < max; i++) {
         List<Integer> ps = primeMap.get(i);

         if (ps == null) {
            //If i is not a key in the map then it is prime
            primes.add(i);

            //i * i is the lowest multiple of i not already in the map
            List<Integer> list = new ArrayList<Integer>();
            list.add(i);
            primeMap.put(i * i, list);
         } else {
            //i is a key in the map, therefore it isn't prime
            //remove the mapping, it's no longer needed
            primeMap.remove(i);

            //reinsert each number in the current value in its new position.
            for (Integer j : ps) {

               int next = i + j;
               List<Integer> nextList = primeMap.get(next);
               if (nextList == null ) {
                  nextList = new ArrayList<Integer>();
               }
               nextList.add(j);
               primeMap.put(next, nextList);
            }
         }
      }
      return primes;
   }

[Gabriel Claramunt]

Garrett Rowe wrote:

Gabriel Claramunt wrote:I guess I overcomplicated a little

No this is over complicating it. Here is a sieve inspired by this paper. (Look ma' no arrays!)

On the other hand, I've used boolean primitive arrays because should be pretty fast. If I recall correctly I did a fancy implementation with collections but it was slow...

[Garrett Rowe]

Gabriel Claramunt wrote:

Garrett Rowe wrote:

Gabriel Claramunt wrote:I guess I overcomplicated a little

No this is over complicating it. Here is a sieve inspired by this paper. (Look ma' no arrays!)

On the other hand, I've used boolean primitive arrays because should be pretty fast. If I recall correctly I did a fancy implementation with collections but it was slow...

I'm quite sure that that method is probably slower than one that uses arrays (I haven't timed it though), I only wrote and shared it as an academic curiosity.

I thought the paper was interesting because the naive (and elegant) SofE is one of those examples that always comes up in Haskell beginners tutorials with no disclaimer that it is likely wildly inefficient and there are better, although not as aesthetically pleasing, ways if implementing it.

[Garrett Rowe]

Garrett Rowe wrote:

Gabriel Claramunt wrote:

Garrett Rowe wrote:

Gabriel Claramunt wrote:I guess I overcomplicated a little

No this is over complicating it. Here is a sieve inspired by this paper. (Look ma' no arrays!)

On the other hand, I've used boolean primitive arrays because should be pretty fast. If I recall correctly I did a fancy implementation with collections but it was slow...

I'm quite sure that that method is probably slower than one that uses arrays (I haven't timed it though)

So for completeness sake, I did finally run some timing tests and the version with boolean[] was ~ 40x faster than the HashMap implementation.

[Brandon Bernie]

	/**
	 * For integer <code>n</code>, the prime generating function,
	 * <code>generatePrimes(n)</code>, will generate a list of prime numbers
	 * upto and uncluding <code>n</code> if <code>n</code> is prime.
	 * 
	 * @param upTo
	 *            positive integer, <code>(upTo >0)</code>
	 *            
	 * @return a list of prime numbers upto <code>n</code>
	 * 
	 * @author Brandon Bernie
	 */
	public static List<Integer> generatePrimes(int upTo) {
		int size = upTo + 1;
		boolean[] flags = new boolean[size];
		List<Integer> primes = new ArrayList<Integer>();
		double limit = Math.sqrt(size);

		// Set flags
		for (int i = 2; i < size; i++) {
			flags[i] = true;
		}

		// Cross out multiples of 2
		int j = 2;
		for (int i = j + j; i < size; i += j) {
			flags[i] = false;
		}

		// Cross out multiples of odd numbers
		for (j = 3; j <= limit; j = j + 2) {
			if (flags[j]) {
				for (int i = j + j; i < size; i = i + j) {
					flags[i] = false;
				}
			}
		}

		// Build list of primes from what is left
		for (int i = 2; i < size; i++) {
			if (flags[i]) {
				primes.add(i);
			}
		}
		
		return primes;
	}

Its decently fast. I am working on a new algorithm that takes into account some number theoretic properties. I used this for solving problems involving small prime numbers over at projecteuler.net.