Program recognizing square numbers as primes [duplicate]

Question

This question already has answers here:

Determining Prime Numbers Java (2 answers)

Closed 8 years ago.

I wrote a program to determine factors of a given number. At first it should of course check if the number is a prime number. This works, but if the number is a square number it recognizes it as a prime...

public class factors {
    public static void main (String [] args) {
        System.out.println("Enter the number you need factors of");
        int base = Kon.readInt();
        for (int i = 2; i < base; i++) {
           int a = base % i;
           if (a == 0) {
             break;
           }
           else {
             System.out.println(base+" is a prime number, so it has no factors");
             break;
           }
        }
        for (int i = 3; i < base; i++) {
            int res = base % i;
            if (res == 0) {
                int fac = base / i;
                System.out.println(i+" and "+fac+" are factors of "+base);
            }
        }
    }
}

So if I enter 64, it says it's a prime, but then tells me that 8 and 8 are factors of 64 in the next line

Does anyone know what the problem might be?

Answer 1

The problem is that you print it's a prime number in your loop, so that you pretend a number is a prime as soon as there's at least one value of i for which base%i is 0.

You should check there's no value of i for which it's true. You might for example do this :

boolean hasFactor = false;
for (int i=2;i<base;i++) {
    int a=base%i;
    if (a==0) {
        hasFactor = true;
        break;
    }
}
if (!hasFactor){
    System.out.println(base+" is a prime number, so it has no factors");
} 

Answer 2

if (a == 0) {
    break;
}
else {
    System.out.println(base+" is a prime number, so it has no factors");
    break;
}

No matter what, you're breaking out of the loop on the first increment. Even if you removed the break; from the else block, you are still displaying whether or not the number is prime too early. You need to decide that after all of the iterations are completed.

So, consider a boolean variable to keep track of whether or not the number has at least one factor in it:

boolean isPrime = true; // true unless proven otherwise
for (int i = 2; i < base; i++) {
    int a = base % i;

    if (a == 0) {
        isPrime = false; // has factor so it's not prime
        break;
    }
}

if (isPrime) {
    System.out.println(base + " is a prime number, so it has no factors");
} else {
    System.out.println(base + " is a composite number: "); // say it's not prime

    // then display the factors
    for (int i = 3; i < base; i++) {
        int res = base % i;
        if (res == 0) {
            int fac = base / i;
            System.out.println(i + " and " + fac + " are factors of " + base);
        }
    }
}

Here is a pastie to this entire class.

Answer 3

The problem is that

if (a==0) {
    break;
} else {
    System.out.println(base+" is a prime number, so it has no factors");
    break;
}

will output that a number is not a prime the moment it's not divisible by i no matter what else, so you must first loop trough it completely before deciding it's not a prime.

So you want to change:

  for (int i=2;i<base;i++) {
      int a=base%i;
      if (a==0) {
        break;
      }
      else {
        System.out.println(base+" is a prime number, so it has no factors");
        break;
      } // end of if-else
    }

into:

  prime = true;
  for (int i=2;i<base;i++) {
      int a=base%i;
      if (a==0) {
        prime = false;
        break;
       }
    }
      if (prime){
        System.out.println(base+" is a prime number, so it has no factors");
      } // not a prime