generating prime number

Question

Anonymous · Accepted Answer

You would be much more efficient using a prime sieve like the sieve of Eratosthenes or Atkins sieve.

If you want to use trial division instead only divide until you get to the square root of the number you are checking. And after checking if the number is divisible by 2 you can start with 3 and only check odd numbers.

100 primes is really a trivial amount so it shouldn't matter, but if the point is to show problem solving skills I would probably go for a sieve of Eratosthenes with a 3,5,7 wheel.

Anonymous · Answer

I would use Fermat's little theorem to test primality

To the person saying FLT · Answer

I think Wilson's Theorem is better. 

In all seriousness I agree with the Sieve of Eratosthenes person. You can also do some math there are about n/lg(n) primes in the first n positive integers so you can bound it is they ask for the first 1000 primes or something.

Ajinkya · Answer

package chapter2;

import java.util.ArrayList;

public class PrimeNumberGenerator {

	public static void main(String[] args) {

		new PrimeNumberGenerator().genPrime(100);

	}

	public void genPrime(int num) {
		ArrayList numbersToCheck = new ArrayList();
		numbersToCheck.add(2);
		numbersToCheck.add(3);
		numbersToCheck.add(5);
		numbersToCheck.add(7);

		int i = 8;
		do {
			boolean isPrime = false;
			boolean isNotPrime = true;
			for (int j : numbersToCheck) {
				if (i % j == 0) {
					isNotPrime = true;
					break;					
					//System.out.println("Inside i%j. I= " + i + ". j = " + j);
				} else {
					isPrime = true;	
					isNotPrime = false;
				}
			}
			if (isPrime && !isNotPrime) {
				numbersToCheck.add(i);
				System.out.println(numbersToCheck);
			}
			i++;
		} while (numbersToCheck.size() < num);
		System.out.println(numbersToCheck);
	}

}

Amazon

Amazon Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches