CODEWITHSUNDEEP
java
Sam
Sam

Reputation: 35

Program to find prime numbers is returning no numbers?

public ArrayList Numbers(int upper, int lower)
{
    ArrayList<Integer> primeNumbers = new ArrayList<Integer>();
    boolean decider;
    for(int x = lower; x <= upper; x++)
    {
        decider = true;
        for(int y = 2; y < upper; y ++)
        {
            if(x % y == 0)
                decider = false;
        }
        if(decider == true)
            primeNumbers.add(x); 
    }
    return primeNumbers;
}

I wrote the following code to determine if a number is prime. My thinking is if i default a boolean to true and a number divided by another number has a remainder of 0, then the boolean is set to false. 

for(int x = lower; x <= upper; x++)
    {
        decider = true;
        for(int y = 2; y < upper; y ++)
        {
            if(x % y == 0)
                decider = false;
        }
        if(decider == true)
            primeNumbers.add(x); 
    }

For this section here, that is what I attempted to do. Every number between the upper and lower bounds is checked to see if any division has a remainder of 0. If it does, the boolean is false and it is not added to my array.

For some reason the array is recieving no numbers between the upper and lower bounds. I cannot spot the problem. Can anyone else?

Edit- I edited this post after finding another error because the program went from returning all values to none at all.

Upvotes: 1

Views: 54

Answers (3)

Emre Acar
Emre Acar

Reputation: 920

This is where the problem is:

for(int x = lower; x <= upper; x++)

When you iterate until <=upper, it also divides the number by itself, and messes up your results.

Change it to "<" and it'll work;

public ArrayList Numbers(int upper, int lower)
{
    ArrayList<Integer> primeNumbers = new ArrayList<Integer>();
    boolean decider;
    for(int x = lower; x < upper; x++)
    {
        decider = true;
        for(int y = 2; y < upper; y ++)
        {
            if(x % y == 0)
                decider = false;
        }
        if(decider == true)
            primeNumbers.add(x); 
    }
    return primeNumbers;
}

Upvotes: 0

Tim Biegeleisen
Tim Biegeleisen

Reputation: 521864

Here is the logical problem I see with your code. Your inner for loop in y will cover most of the time a range which includes the value of x, since the loop's upper bound is also upper. So, in most cases, you would be counting a number divisible only by itself as being not prime, when in fact it is. You should stop that loop before reaching the target x. And also, you may break if you find a divisor.

for(int x = lower; x <= upper; x++) {
    decider = true;
    for (int y = 2; y < x; y ++) {   // can probably make this bound even tighter
        if (x % y == 0) {
            decider = false;
            break;
        }
    }
    if (decider)
        primeNumbers.add(x); 
}
return primeNumbers;

Here is a demo showing that the above logic works correctly:

Demo

Upvotes: 1

Haris Nadeem
Haris Nadeem

Reputation: 1314

The issue is that you are writing the wrong arguments when scanning through y. Observe:

public ArrayList Numbers(int upper, int lower)
{
    ArrayList<Integer> primeNumbers = new ArrayList<Integer>();
    boolean decider;
    for(int x = lower; x <= upper; x++)
    {
        decider = true;
        for(int y = 2; y < x; y ++)
        {
            if(x % y == 0)
                decider = false;
        }

        if(decider = true)
            primeNumbers.add(x); 
   }
   return primeNumbers;
}

Of course you could improve your code by keeping the upper bound of y as the sqrt(x) + 1 and adding y by increments of 2 instead of 1. You need to check the base case of the number 2 separately.

Upvotes: 0

Related Questions