2
\$\begingroup\$

I am creating a class which should contain all the methods related to Prime numbers. Now in that I have to implement a method isPrime() to check the primality of a number. I have to implement that in two ways one that uses the Sieve of Erastosthene and one that uses the standard for looping. The class should be made in such a way that If I use a specific constructor to instantiate it then it should use the sieve algorithm. If I use the other constructor then it should use the standard way of finding primality (through looping). Now I made this implementation keeping conceptual affinity in mind. I have made inner classes to implement both the types of implementations. Is this is the best way to do this, or should I use separate classes?

import java.util.Arrays;

/**
 * Class for Prime Number related methods.
 */
public class PrimeNumber {

    private PrimeAbstract primeNumber;

    /**
     * If you want the class to use <code><b>sieve of erastosthene</b></code> as the
     * base algorithm then you need to use this constructor. You need to pass the
     * limit till which you want the sieve to be initialized as the method parameter.
     * @param limit
     */
    public PrimeNumber(int limit) {
        this.primeNumber = new PrimeNumberWithSieve(limit);
    }

    /**
     * If you want the class to use the classic way of finding out the primality
     * of a number. By classic we mean for looping.
     */
    public PrimeNumber(){
        this.primeNumber = new PrimeNumberClassic();
    }

    /**
     * Returns if a number is prime or not.
     * @param number
     * @return boolean
     */
    public boolean isPrime(int number){
        return primeNumber.isPrime(number);
    }



}

/**
 * abstract class of prime number object
 */
abstract class PrimeAbstract {

    public abstract boolean isPrime(int number);
}




/**
 * This class uses <code><b>sieve of erastothene</b></code> as the base
 * algorithm for finding out the primality of a natural number.
 */
class PrimeNumberWithSieve extends PrimeAbstract {

    boolean[] sieve;

    public PrimeNumberWithSieve(int limit){
        sieve = limit<1000?new boolean[1001]:new boolean[limit+1];
        Arrays.fill(sieve, true);
        sieve[0]=sieve[1]=false;
        for (int i=2;i<sieve.length;i++) {
            if(sieve[i]) {
                for (int j=2;i*j<sieve.length;j++) {
                    sieve[i*j]=false;
                }
            }
        }
    }

    /**
     * This method returns if a number is prime or not.
     * It uses the sieve of erastothene method to figure this out.
     * The sieve is declared in the class and initialized on instantiating
     * the class.
     * @param number
     * @return
     */
    public boolean isPrime(int number){
        return sieve[number];
    }
}

/**
 * This class uses standard for looping for finding out the primality of a number.
 */
class PrimeNumberClassic extends PrimeAbstract{

    public PrimeNumberClassic(){
    }

    /**
     * This method returns if a number is prime or not.
     * It uses the classical style of for looping through all the numbers
     * till the <b>sqaure root</b> of the number.
     * @param number
     * @return
     */
    public boolean isPrime(int number) {
        if (number%2==0) return false;
        for(int i=3;i*i<=number;i+=2) {
            if(number%i==0)
                return false;
        }
        return true;
    }

}
\$\endgroup\$
3
\$\begingroup\$

Bugs in PrimeNumberClassic

There are multiple bugs in this class : 2 is not prime, while any number <= to 1 are considered prime :(

Some large number may results in infinite loop !!! (I'm going into more details about that at the end of my post)

Before considering the rest of my reviews, you should :

  • correct them
  • make unit tests (check JUnit) for your two classes for some cases (2, multiple even numbers not 2, 3, 5, 7, 31, 277, some really big numbers and a negative number for example)

Consider using bigger number

int aren't that big, if you plan on doing math calculations, you should consider switching to long or BigInteger.

Well now, the real review :

Review of PrimeNumber

I don't really get what this class is about. The name makes it sounds like it's storing a prime number but it's not... it actually looks like a Factory of some sort.

I'd consider removing it unless you want to add more features (in which case that may be the object of a future, follow-up, question ^^).

Review of PrimeAbstract

/**
 * abstract class of prime number object
 */
abstract class PrimeAbstract {

    public abstract boolean isPrime(int number);
}

Why is this an abstract class ? It's clearly an interface, also the javadoc is pretty useless.

The name is not very good... why PrimeAbstract ? Aren't PrimeNumberFinder/ PrimeNumberDetector name closer to the intent ?

Review of PrimeAbstract's childs

The code in the implementation really needs to breathe !

Put some spaces in it ;) it's tiring to read it as of now.

As a rule of thumb, put spaces between the = (as well as things like += ofc) sign, the '?' sign and theirs operands as well as between comparators and their operands.

if (number%2==0) return false;

I'm one of the people that don't really care about using { for very simple cases... however putting the return on the same line makes it harder to read IMO.

As said in others questions, any good IDE have a code formatter included solving all previous points (and auto-indenting your code) ;)

The Sieve is okish... I don't really like the fact that it fails with an exception when you use isPrime with a too big number. Also you should make the field private ;)

I'd probably make the sieve lazy and not compute it until isPrime is called for the first time.

1000 is a magic number and should be turned into a constant.

Finally, storing every results in an array is really space-inefficient. Maybe consider storing only the integers that are prime into an HashSet, the contains method with a HashSet is incredibly fast.

I'd optimize PrimeNumberClassic to :

  • know the results for some very small primes (reducing the complexity for "common" cases)
  • go for at most sqrt of number... yeah I know you already do that with i*i but it's less clear, likely less performant and it's buggy (if i grows large it'll overflow and you find yourself with a potentially infinite loop or accessing indexes that aren't in your array... no good)

So in the end this implementation may look like something like :

public boolean isPrime(final int number) {
    if (number == 2) {
        return true;
    } else if (number % 2 == 0) {
        return false;
    } else if (number < 36) {
        return number == 3 || number == 5 || number == 7 || number == 11 || number == 13
                || number == 17 || number == 19 || number == 23 || number == 29 || number == 31;
    }

    final int max = (int) Math.round(Math.sqrt(number));
    for (int i = 3; i <= max; i += 2) {
        if (number % i == 0)
            return false;
    }
    return true;
}
\$\endgroup\$
6
  • \$\begingroup\$ the requirement is to make the class in such a way that if I call the constructor 'public PrimeNumber(int limit)' it should use the sieve logic and if I use the other constructor it should do it in the standard looping way.Also I totally get you on naming convention I made this in quite a hurry. Client pressure! \$\endgroup\$ Jun 16 '17 at 13:07
  • \$\begingroup\$ @AdityaCherla ok :) then you should leave it as it is ;) (what you actually have a client asking you to make a prime number finder ? ^^) \$\endgroup\$ Jun 16 '17 at 13:09
  • \$\begingroup\$ this is for some component that he is about to use in some mobile app. Anyways thanks a lot the review! I'll make the changes and present it to him. \$\endgroup\$ Jun 16 '17 at 13:13
  • 1
    \$\begingroup\$ @GoJava That was my point ?... which is why I put it after a "bug" disclaimer. I said that, in the code shown in the question, 1 was considered prime while it's not and 2 is not considered prime but should be, which is why the code I propose at the end correctly give "true" for 2 and "false" for 1. \$\endgroup\$ Jun 16 '17 at 17:31
  • 1
    \$\begingroup\$ @GoJava no problem, I'll edit to make it clearer ;) \$\endgroup\$ Jun 16 '17 at 17:48
0
\$\begingroup\$
  1. In my equivalent class, I find nextPrime(int num) and previousPrime(int num) to be useful, the first more than the second. They return the next higher prime and the next lower prime respectively.

  2. Using a boolean array is horribly inefficient use of space. Better to use a BitSet which only uses one bit per number. With a little extra coding you can reduce that to half a bit per number by only holding odd numbers in the sieve.

  3. Your PrimeNumberClassic.isPrime() fails to flag 2 as prime.

Here is a better version with more spaces in the code to make it easier to read:

public boolean isPrime(int number) {
    if (number < 2) {
        return false;
    }
    if (number % 2 == 0) {
        return number == 2;  // 2 is the only even prime.
    }
    for (int i = 3; i * i <= number; i += 2) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

If you have the sieve in place, then you can use a similar method to test numbers between the limit of the sieve and its square:

for (int i = 3; i * i <= number; i = sieve.nextPrime(i)) {
    if (number % i == 0) {
        return false;
    }
}

This uses the nextPrime() method I suggested above, and avoids dividing by odd composite numbers like 15 or 27.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you for telling me about BitSet and yes 'nextPrime' and 'previousPrime' methods seem to be the reasonable thing to do. \$\endgroup\$ Jul 6 '17 at 5:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.