Prime test, 2-digit numbers

Question

Hi,

I want to print all prime numbers that are 2-digits long. Here is my code:

    for(int input = 11; input <= 99; input += 2){
        for(int x = 2; x < (int)Math.sqrt(input) + 1; x++){
            if(input%x != 0){
                System.out.println(input);
                break;
            }else{
                break;
            }
        }
    }

The problem is that it prints numbers like 35 or 49 which are not prime numbers.

any ideas?

Answer 1

Wikipedia gives a good algorithm for finding prime numbers. It also lists those up to 100.

If you are looking for debugging help, I would simply step through your code until you see which of your tests are not correct. This is a quick simple program and shouldn't take you long.

Answer 2

for(int input = 11; input <= 99; input += 2){
    int found = 0;
    for(int x = 2; x < (int)Math.sqrt(input) + 1; x++)
        if(input%x == 0){
            found = 1;
            break;
        }
    if(found == 0)
        System.out.println(input);

}

this should do the work

Answer 3

You are printing all the odd numbers. You always break out of the loop so x never exceeds 2.

if(input%x != 0){
    System.out.println(input);
    break;  // <<-- break here
}else{
    break;  // <<-- and break here
}

Also think carefully about the definition of a prime number:

• If any of the numbers you test is an exact divisor the number is not prime.
• If all of the numbers you test are not exact divisors then the number is prime.

You should only break out of the loop if you found a divisor. If you haven't found one yet you need to keep going until you have tested all the possibilities. And you shouldn't print anything until you've finished the loop and know the result.

Answer 4

Your test for primeness is incorrect. You stop testing a number (input) as soon as you find a divisor which the input is not divisible by.

That's not the definition of prime - you need to test that the input number is not divisible by any divisors less than it - in other words you need to test all values of x before you can declare a number as prime.

You can break out of the loop that checks input % x != 0 when an input is divisible by x, but not when it is not divisible - you need to keep on checking when this condition is true!

Answer 5

Yes because it is printing out all cases where a non-factor is found. You need to ONLY print out cases where no factors can be found.

Answer 6

This works. You can see the output here.

public class Main {

public static void main(String[] args) {
for(int input = 11; input <= 99; input += 2){
    boolean found = false;
    for(int x = 2; x < (int)Math.sqrt(input) + 1; x++){
        if(input%x == 0){
            found = true;
            break;
        }

    }
    if(!found) {
            System.out.println(input);
    }
}
}
}

Answer 7

I always love questions where the shortest and most obvious answer is to just hardcode the output:

System.out.println("11\n13\n17\n19\n23\n29\n31\n37\n41\n43" +
   "\n47\n53\n59\n61\n67\n71\n73\n79\n83\n89\n97");

Answer 8

The problem is in this block:

if(input%x != 0)
{
System.out.println(input);
break;
}

It will print 'input' if it is not divisible by current value of 'x', but it may be divisible by next values of 'x'. In that case 'input' is not prime, but it is printed.

Correct code:

boolean flag;
for(int input = 11; input <= 99; input += 2)
{
        flag = true;
        for(int x = 2; x < (int)Math.sqrt(input) + 1; x++)
        {
            if(input%x == 0)
            {
                flag = false;
                break;
            }
        }
        if(flag == true)
            System.out.println(input);
}

Answer 9

To find a prime, you don't need to test every numbers below it up to it's square root; you simply need to test every other prime below it. Here's a demo :

ArrayList<Integer> primes = new ArrayList<Integer>(); // hold every other prime numbers that we find
boolean isPrime;

// add first base prime number
primes.add(2);

for (int x = 3; x < max; x+=2) {  // start from 3 and skip multiples of 2
    isPrime = true;  // prove it's not prime
    for (Integer i : primes) {
        if (x % i == 0) {
            isPrime = false; // x is divisible by a prime number... 
            break; // exit loop, we proved it's not a prime
        }
    }
    if (isPrime) {
        if (x >= 10) {
            System.out.println(x);  // print only two digits prime numbers
        }
        primes.add(x);  // add x to our prime our number list for future checks
    }
}

** EDIT **

A yet more flexible and reusable implementation in a static method (not optimized for listing large prime numbers) :

public static List<Integer> findPrimes(int min, int max) {
    LinkedList<Integer> primes = new LinkedList<Integer>();
    boolean isPrime;
    double square;

    // add first base prime number
    primes.add(2);

    for (int x = 3; x < max; x+=2) {  // start from 3 and skip multiples of 2

        isPrime = true;  // prove it's not prime
        square = Math.sqrt(x);
        for (Integer i : primes) {
            isPrime = x % i != 0;  // x is not prime if it is divisible by i
            if (!isPrime || i > square) { 
                break;
            }
        }
        if (isPrime) {
            primes.add(x);  // add x to our prime numbers
        }
    }

    // remove all numbers below min
    while (!primes.isEmpty() && primes.getFirst() < min) {
        primes.removeFirst();
    }

    return primes;
}

Method usage :

List<Integer> primes = findPrimes(10, 100);
System.out.println("Listing " + primes.size() + " prime numbers");
for (Integer prime : primes) {
    System.out.println(prime);
}