Use Modulus Operator to Get Prime Numbers

Question

How would you modify the below to print out all prime numbers from 1-100? The below has an issue with the number 2 coming back as not prime. The if(i%number == 0) condition is met for the number 2 as 2%2 is returned as 0.

public class Test {

    /**
     * @param args
     */
    public static void main(String[] args) {
        for(int i=1; i<=100; i++){
            if(isPrime(i)){
                System.out.println(i + " is a prime number");
            }else{
                System.out.println(i + " is not a prime number");
            }
        }

    }
    public static boolean isPrime(int number){
        for(int i=2; i<=number; i++){

            if(i%number == 0){
                return false;
            }else{
                return true;
            }
        }
        return false;
    }

}

You are asking this why exactly? What have you tried, what has not worked? — Micha Wiedenmann, Jul 23 '13 at 17:32
Your for loop in isPrime is broken. It always returns within the first iteration. Also pls debug my code questions are usually not sutable for this site. — ClassicThunder, Jul 23 '13 at 17:34
@ClassicThunder He's asking why it doesn't work as expected (thus where's the logic error). Looks like a completely legit question to me. — m0skit0, Jul 23 '13 at 17:37
The fact that the question is about logic does not make it OK to ask: "Please debug the following code for me" questions. — Eric Leschinski, Jul 23 '13 at 17:55
possible duplicate of [What would be the fastest method to test for primality in Java?](http://stackoverflow.com/questions/2385909/what-would-be-the-fastest-method-to-test-for-primality-in-java) — Has QUIT--Anony-Mousse, Jul 23 '13 at 18:07

score 2 · Accepted Answer · answered Jul 23 '13 at 17:33

 i<=number

You shouldn't be checking whether the number is divisible by itself.

You also have another problem:

        }else{
            return true;
        }

You're returning true as soon as you find a single non-divisible number, even if it does have factors later.

Gilbert Le Blanc · Answer 2 · 2020-06-04T22:14:45.383

2

Here is an algorithm for determining whether or not a number is prime.

Is the number less than 2? If so, return false.
Is the number 2 or 3? If so, return true.
Is the number 4? If so, return false.
Take the square root of the number, rounded up to the next integer. This is optional for small prime numbers, but speeds up the determination for larger numbers.
Loop from 5 to the square root of the number (or the number), incrementing by 2.
- Divide the loop number by the prime numbers determined so far.
- If the modulus of the division is zero, return false.
If the loop is completed, return true.

edited Jun 04 '20 at 22:14

answered Jul 23 '13 at 17:50

Gilbert Le Blanc

50,182
6
67
111

old thread I know, but where does this come from? Is there a source? – orionrush Jun 04 '20 at 21:58
I wrote this nearly seven years ago, so if there was a source, I don't remember. The square root trick is pretty common. You can also increment the for loop by two and avoid the divide by 2 tests. – Gilbert Le Blanc Jun 04 '20 at 22:13

Slater Victoroff · Answer 3 · 2013-07-23T17:49:42.450

1

You've got a couple issues here. Firstly, when checking whether or not a number is prime, never check every number up to the actual number being checked for primality. A check of all primes up to the square root of the number will always be sufficient.

To fix that error look at your for loop condition and edit it accordingly:

for(int i=2; i<=number; i++)

Secondly, when a function returns it stops. Currently with your if/else statement:

if (i%number == 0) {
   return false;
} else {
   return true;
}

If this condition goes to the else statement even once it will return true, you want to make sure you only actually return true when you've checked all of the numbers you intend to.

Additionally I don't think you've carefully considered what you base case is. What you are saying with your last line is that if everything previously slipped through the cracks then it should assume the number isn't prime. Think about it and I'm sure you'll be able to figure it out.

edited Jul 23 '13 at 17:49

answered Jul 23 '13 at 17:34

Slater Victoroff

21,376
21
85
144

You can just replace all your code with `return false;` ;) Fix the typo. – m0skit0 Jul 23 '13 at 17:35
While this is an answer, you're doing OP's work. Refer to http://meta.stackexchange.com/q/10811/182862 – Luiggi Mendoza Jul 23 '13 at 17:35
@LuiggiMendoza Wasn't aware that this was homework, will edit to be less of a hand out – Slater Victoroff Jul 23 '13 at 17:36
It's not hard to realize this is a homework (I doubt you solve this kind of problems at work) – Luiggi Mendoza Jul 23 '13 at 17:37
@LuiggiMendoza yea, probably shoulda caught it, but it's been a long day. Updated to be more feedback and less of a hand out. – Slater Victoroff Jul 23 '13 at 17:40

null · Answer 4 · 2013-07-23T18:02:19.660

This will work. 2 is a special case when testing for primes. If you start to search a larger and larger...you might want to look at the sieve of eratosphenes.

Every prime number is a multiple of another number. Take 3 for example. Using the sieve, if you find 3 to be prime it will then 'ignore' all multiples of 3 thus reducing the amount of time taken to find consequent primes. It speeds things up...ALOT :)

 public class JavaApplication47 {

 public static void main(String[] args) {

    for(int i=1; i<=100; i++){
        if(isPrime(i)){
            System.out.println(i + " is a prime number");
        }else{
//                System.out.println(i + " is not a prime number");
        }
    }
}

public static boolean isPrime(int n) {
for(int i=2; 2*i<n; i++) {
    if(n%i==0)
        return false;
}
return true;
}
}

SIEVE EXAMPLE - NOT IMPLEMENTED - Can be used for reference and understanding.

static boolean [] allPrimes = new boolean[10000];

public static void fillTheSieve(){
    Arrays.fill(allPrimes, true);
    allPrimes[0] = allPrimes[1] = false; //1 and 0 are false. winning

    for (int i = 2; i < allPrimes.length; i++) {
        //check if prime, if so getmultiples and declae false
        if(allPrimes[i]){
            for (int j = 2; i*j<allPrimes.length; j++) {
                allPrimes[i*j] = false;

            }
        }

    }
}

score 0 · Answer 5 · answered Jul 23 '13 at 17:38

The definition of a prime number specifically states that one cannot be a prime number.

That means that isPrime(1) should return false. Which your implementation does.

But isPrime(2) should return true. Which your implementation does not. It does not because (2 % 2 == 0) and you are checking all numbers from 2 to N, not from 2 to N-1. The last number, N, will always yield a zero remainder (N % N == 0)

score 0 · Answer 6 · answered Jul 23 '13 at 17:43

Just a few things to think about when dealing with Primes. You can have a special case for 2 at the start (i.e. something like if(number == 2)...).

In addition to your error in checking all the way to i<=number consider only how far you need to go in order to be certain it is not prime, hints have already been given with i*i or Math.sqrt

Another thing in the increment i++ think about what that entails, I realize this is only for the first 100 primes but you should always be thinking about performance. Do you really have to check all numbers (2,3,4,5,6...) (hint: if you have checked if its divisible by 2 then you dont need to check for 4,6,8 etc..)

Finally with your return statements, consider using a boolean flag that you set to false/true only when you are positive the number is a prime or is not. And you only need to use 1 return statement.

Hope that helps.

score -4 · Answer 7 · answered Jul 23 '13 at 17:34

-4

Please try this

public static boolean isPrime(int number) {
    for(int i = 2; i * i <= number; i++) {
        if (i % number == 0) {
            return false;
        } else {
            return true;
        }
    }
    return true;
}

answered Jul 23 '13 at 17:34

seanxiaoxiao

1,282
2
11
23

Please don't try this... it's also broken. – MobA11y Jul 23 '13 at 17:35
Plese refer to http://meta.stackexchange.com/q/10811/182862 before posting such answers (also, you might review what you post as well) – Luiggi Mendoza Jul 23 '13 at 17:36

Use Modulus Operator to Get Prime Numbers

7 Answers7