Generate prime number between m to n

,
1

why we do j<=i/2 ?

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin>>t;
    
    while(t--){
        int m,n;
        cin>>m>>n;
        int flag;
        
        for(int i=m;i<=n;i++){
            if(i==0||i==1)
            continue;
            
            flag=1;
            
         **for(int j=2;j<=i/2;j++){**         
                if(i%j==0){
                flag=0;
                break;
                }
            }
            
            if(flag==1)
            cout<<i<<"\n";
        }
    }
    return 0;
}
2

instead of “j<=i/2”
We write j<=sqrt(i).
suppose we are checking for i=30
if we see its sqrt which will be 5.47722558…
so if any number greater than this would be divisible by 30,
then, there would be surely present some number smaller than sqrt(i) which is also divisible by that number.
So if we see 6 is divisible by 30
we say 6x5=30
So here 5 is smaller than sqrt(i)
next if we say 10 is divisible by 30
or we can say 10x3=30
so 3 is also divisible by 30.

If we could not get any number divisible by i till sqrt(i)
there would be no any other number divisible by i.
and can say its prime number.

2 Likes
3

go for segmented sieve

4

If we use sqrt(i)
Can you tell me the complexity

O(n*sqrt(n))

5

Ohk

6

Yes it will become O(n srt(n))