Java - simple program (find primes) - does not run

2

I'm starting to learn java, I'm using the Java book in Beguinners Guide and it appeared that little problem to find the cousins from 1 - 100 and print on the screen. I made the following code.

class AllPrime {
    public static void main(String args[]) {
        int i;
        int counter = 0;
        int k;

        for(i = 1; 1 <= 100; i++)
        {
            for(k = 1; k <= i; k++)
            {
                if( (i % k) == 0)
                    ++counter;  
            }
            if( counter == 2 )
                System.out.println("The number: " + i + "is prime");
        }
    }
}

You did not print anything on the screen. I have read and reread this code and can not understand what is wrong. It compiles just does not spin.

    
asked by anonymous 08.11.2015 / 21:44

5 answers

6

You made some silly little mistakes.

  • Your big mistake is that you do not make counter back to zero after iterating a number in i . Because of this, after deciding that 1 is not prime, it will never be able to decide that any number is prime, since counter never decreases.

  • Another problem was the stopping condition of for that was 1 <= 100 instead of i <= 100 .

  • Finally, you can declare the variables i and k within the for itself, you do not need to declare before.

  • Failed to add a space before "is prime" .

So here is your corrected code.

public class Main {
    public static void main(String args[]) {
        for (int i = 1; i <= 100; i++) {
            int counter = 0;
            for (int k = 1; k <= i; k++) {
                if (i % k == 0) ++counter;
            }
            if (counter == 2) {
                System.out.println("The number: " + i + " is prime");
            }
        }
    }
}

You can also optimize your code a bit more because you never need to test whether the number is divisible by 1 or by itself, because it always will be. This way, you no longer need to count the divisors, as soon as you find a divisor you already know that the number is composed and you do not have to waste time testing the other numbers, you can use continue to move on to the next iteration. This also eliminates the need for the counter variable. This way, your code looks like this:

public class Main {
    public static void main(String args[]) {
        out: for (int i = 1; i <= 100; i++) {
            for (int k = 2; k < i; k++) {
                if (i % k == 0) continue out;
            }
            System.out.println("The number: " + i + " is prime");
        }
    }
}

You can further optimize if you verify that if the number is composed, then at least one of the divisors is less than or equal to the square root of the number. So, if until you get to the square root, you find no divisor, it's because the number is prime. Logo:

public class Main {
    public static void main(String args[]) {
        out: for (int i = 1; i <= 100; i++) {
            for (int k = 2; k <= Math.sqrt(i); k++) {
                if (i % k == 0) continue out;
            }
            System.out.println("The number: " + i + " is prime");
        }
    }
}

There are other possible mathematical tricks, especially to avoid testing values of k that are composed and also to compute the entire square root that is faster than the square root of floating point. Other properties of prime numbers and composites can be used to reduce computational effort. However, these more aggressive optimizations would no longer be simple, and you probably want an algorithm that is quite simple, even more so that you are only testing cousins up to number 100.

    
08.11.2015 / 22:00
3

The error is in the fact that you are not restarting the value of the variable counter for each i .

See:

  • The code starts with counter == 0 .
  • When i == 1 and k == 1 , i % k == 0 . Therefore, counter++ ( counter == 1 ).
  • k is incremented, and exits for .
  • When i == 2 and k == 1 , i % k == 0 . Therefore, counter++ ( counter == 2 ).
  • When i == 2 and k == 2 , i % k == 0 . Therefore, counter++ ( counter == 3 ).
  • k is incremented, and exits for .

Notice that counter > 2 ( counter == 3 ). By induction, the message will never be printed, since counter will only grow and has already exceeded the expected value for printing the message.

Restarting the value of counter in each iteration in i solves the problem:

class AllPrime {
    public static void main(String args[]) {
        int i;
        int k;

        for(i = 1; i <= 100; i++)
        {
            int counter = 0;
            for(k = 1; k <= i; k++)
            {
                if( (i % k) == 0)
                    ++counter;  
            }
            if( counter == 2 )
                System.out.println("The number: " + i + "is prime");
        }
    }
}
    
08.11.2015 / 21:59
1

You could do this by making a static isPrime method, so your code is simpler, more organized, and readable:

public class Main {

    public static void main(String args[]) {

        for (int i = 1; i <= 100; i++) {
           if (isPrime(i)) {
               System.out.println("The number: " + i + " is prime");
           }

        }

    }

    public static boolean isPrime(int x) {

       int count = 2;

       for (int i = 2; i < x; i++) {
          if (x % i == 0) {
              count++;
          }
       }

       return count == 2;

    }

}
    
08.11.2015 / 22:29
1

Complementing the previous answers, which are by the way already quite complete, I would like to leave an example where you have the possibility to leave your code a little more flexible, where you can determine the interval in yourself who wants to check all prime numbers, and gives you another way to visualize other perspectives on this problem.

import java.io.*;

public class AllPrime {
    public static void main(String args[]) throws IOException {

        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

        int minimo;
        int maximo;

        System.out.println("****************************");
        System.out.println("Digite um intervalo: ");
        System.out.println("****************************");

        System.out.println("\nMinimo: ");
        minimo = Integer.parseInt(input.readLine());

        System.out.println("\nMaximo: ");
        maximo = Integer.parseInt(input.readLine());

        for (int i = minimo; i <= maximo; i++)
            if (isPrime(i)) imprimir(i);

    }

    public static boolean isPrime(int number) {
        int count = 2;

        for (int i = 2; i < number; i++) {
           if (number % i == 0) {
               count++;
           }
        }
        return count == 2;
    }

    public static void imprimir (int number) {
        System.out.println("The number: " + number + " is prime");
    }

}
    
09.11.2015 / 12:02
0
System.out.println("Digite um numero:");
    int numero = scan.nextInt();

    int diferença = 0;

    for (int i = 1; i < numero; i++) {

        if (numero % i == 0) {
            diferença ++;
        }
    }

    if (diferença == 1) {
        System.out.println(numero +  " É Primo");
    }else {
        System.out.println(numero + " Não é primo");
    }
}
    
04.10.2018 / 14:31