New course! Every coder should learn Generative AI!
Try a free lesson+ 1
Finding prime numbers between two numbers
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"); } }} -----------------------------------------------------------------------
2 Answers
+ 2
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...
+ 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.