Finding prime numbers between two numbers

Question

Hello everyone,

I understood nearly everything except the part: " for(int j=2; j<=(i/2)+1; j++) "
2 is the lowest prime number; that's why we used j=2. But I couldn't understand where this one came from, like what bases they took to create this line: "j<=(i/2)+1".
Can someone please explain it to me? Thank you in advance!

Here is the full code:
-----------------------------------------------------------------------
public class Codes {
public static void main(String[] args) {

int a = 21;
int b = 90;

for (int i = a; i < b; i++)
{
boolean asal=true;
for(int j=2;j<=(i/2)+1;j++)

if(i%j==0)
{
asal=false;
break;
}
if(asal)
System.out.println(i+"\t");

}

}}

-----------------------------------------------------------------------

Answer 1

For any number, you don't find factors n/2+1 to n-1. Check this :
Ex:
10 : 1,2,5,10
20: 1,2,4,5,10,20
100: 1,2,4,5,10,20,25,50,100
So you can skip range after n/2+1.
Hope it helps to understand it...

edit:

no factors between 5, 10. ( n/2, n) for 10.
no between 10,20 for 20
no between 50,100

and additionally :
@Schindlabua said :
39 => 1,3,13,39
1*39
3*13
as √39 = 7, checking between 1 to 7 inclusive , is enough instead of 1 to 20 : (n/2+1).

if n = i * j then if you pick i, j both as factors, it's enough to check j <= sqrt(i);
so j<=sqrt(i) is enough...

Answer 2

Factors come in pairs.
39 = 3 * 13

If you have checked that 39 is divisible by 3, you automatically know that it is divisible by 13 also!

So, if you run your loop all the way up to `i`, you can safely skip the number 13 in your loop because you know your number *must* be divisible by 13.

Can we skip 14 aswell? Yes!

Factor pairs always contain a large and a small number.

In case 39 = j * 14, you would have already encountered a smaller j earlier in the loop. Since you didn't, you know that 39 isn't divisible by 14.

Repeat for i>14.

So... how far do you have to run the loop? Actually it's √i, rounded up.

√39 ≈ 7

Because, recall, factor pairs have a bigger and a smaller number. If you make j larger than the square root, then suddenly j would be the larger factor.

Actually, look at Jayakrishna🇮🇳's example for 100. You'll see 10 = √100 is in the middle of the list, and the other factors pair up nicely.

i/2+1 is bigger than √i, so that works too, but your loop is actually doing too much work.