Program that checks if given number is prime number

Question

Hello i got little program here that checks if given number is prime number, but i dont understand some part in for loop and i need your help. here is the code:

public class PrimeNumber
{
    public static void main(String args[])
    {

        int number;
        boolean prime;
        /*
            *is a natural number greater than 1 that has no positive divisors other 
            *than 1 and itself.
            * such as: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 
            * 61, 67, 71, 73, 79, 83, 89, 97, 101, and so on.
            */
        number =23;

        if(number<2)  
            prime=false; 
        else
            prime=true; 
        for(int i=2; i <=number/2; i++) 
        {
            if ((number%i) ==0) 
            { 
                prime =false; 
                break;
            }
        }
        if(prime) System.out.println("It is prime number");
        else System.out.println("it is not prime number");
    }
}

I understand that first if function checks if given numbers is higher than 2 if it is not prime will be false, if it will prime will be true. Then in for loop i think int is 2 because 2 is the smallest possible prime number ? I understand <= this operator checks if i is less than or equal to number but i dont understand why we used number/2 ? and why we had to check if there is rest between these two numbers in last if function ?

The code is poorly written so I can't tell you why you did those things rather than use a much more efficient and widely available solution. If you want to understand your code, I suggest you try using a debugger or changing it and see what difference it makes. — Peter Lawrey, Nov 18 '13 at 21:48
When you say `we` it begs the question; why don't you ask the person who wrote it why they did what they did? — Peter Lawrey, Nov 18 '13 at 21:49
Look up the [Sieve of Eratosthenes](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) — Edward, Nov 18 '13 at 21:51
Yeah, there might be better solution for this but i dont know, i am just beginner and this is the first time i write program for prime numbers. — Miljan Rakita, Nov 18 '13 at 21:53
@Milan IMHO you should throw away that book. When an error like that is done on a such algorithm, I'm afraid about the more important thing that could not be taken care. You check first if number if the number is even and then you loop `for(int i=3; i <=sqrt(number); i=i+2)` — Luc M, Nov 18 '13 at 21:58

score 3 · Answer 1 · edited May 23 '17 at 10:31

3

The author checks only up to n/2, because if 2 is the smallest possible factor, then n/2 is the largest possible ~~factor~~ divisor(?). While it is not the largest possible factor, the algorithm writer knew for sure that no factor could possibly be larger than n/2.

The author then uses n % i == 0 to check if the number is divisible by any number in the range. If it is, it is definitely not a prime.

Keep in mind this is not the most efficient way of prime checking. See Which is the fastest algorithm to find prime numbers?

edited May 23 '17 at 10:31

Community

1
1

answered Nov 18 '13 at 21:50

Rotem

21,452
6
62
109

In fact, the largest possible divisible number is `ceil(sqrt(number))`, not `number/2`. – Luiggi Mendoza Nov 18 '13 at 21:52
5

In fact, the largest non-trivial divisor of 26 is 13, which is larger than ceil(sqrt(26)). – Don Roby Nov 18 '13 at 21:55
@DonRoby if you're that technical, the largest factor of 26 is 26 :). – Luiggi Mendoza Nov 18 '13 at 21:56
1

@DonRoby While true, you would eliminate 26 earlier than that, as it is divisible by 2. – Rotem Nov 18 '13 at 21:56
4

It's inefficient because you only need to check factors up to `ceil(sqrt(number))` because any factor greater than that would already have been checked implicitly because it would need to be paired with one less than that. – Austin Salonen Nov 18 '13 at 21:57
@AustinSalonen OP is not asking for an efficient prime number function, he's asking what the posted code does and why. – Rotem Nov 18 '13 at 21:58
Yes, you only have to check factors up to ceil(sqrt(number)). But there are greater divisors. – Don Roby Nov 18 '13 at 21:58
@Rotem: No doubt. I was really just clarifying the point made by @Luiggi w/r/t the sqrt as to why typical prime number checkers stop at a certain value that isn't always `number/2`. – Austin Salonen Nov 18 '13 at 22:00

score 0 · Answer 2 · answered Nov 18 '13 at 21:57

you need to check that number does not have any divisors other than 1 and itself, and if you checked all integers until number/2, then obviously, you don't need to check more numbers since i can not be a divisor of number for i>number/2 if number/i is not a divisor.

with the same logic, you can make it more efficient by replacing this line:

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

with this line:

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

Program that checks if given number is prime number

2 Answers2