Why do j need to be smaller or equal to sqrt(i)?

Question

I need to write a c++ program to find prime number within the range. But I don't know what the meaning of this code: j<=sqrt(i)

int main() {
    int num1,num2;
    int fnd=0,ctr=0;

    cout << "enter first number: ";
    cin >> num1;

    cout << "Enter second number: ";
    cin >> num2;

    for(int i=num1;i<=num2;i++)
    {
        for(int j=2;j<=sqrt(i);j++)
        {
            if(i%j==0)
                ctr++;
        }
        if(ctr==0&&i!=1)
        { fnd++;
            cout<<i<<" ";
            ctr=0;
        }
        ctr=0;
    }
}

Probably better to think about attributes of a composite number - it has at least one factor other than itself and `1`. For every factor less than or equal to `sqrt(i)` there will be another factor greater than or equal to `sqrt(i)` and vice versa. If no factor is found that is less than or equal to `sqrt(i)`, there cannot be a factor that is greater than or equal to `sqrt(i)`. (And, if `sqrt(i)` is a factor of `i`, it is because it can be multiplied by itself to give `i`). — Peter, Sep 21 '19 at 10:47

score 0 · Answer 1 · answered Sep 21 '19 at 10:41

Let's assume that you want to check whether the number 25 is a prime number.

if you will write like

for ( int j = 2; j < sqrt( 25 ); j++ )
{
    //...
}

then you will get that 25 is a prime number! It is because j equal to 5 (and 5 * 5 yields 25) does not take part in the iterations of the loop. For j equal to 5 the condition j < sqrt( 25 ) evaluates to false.

So in the loop you have to write

for ( int j = 2; j <= sqrt( 25 ); j++ )
                   ^^
{
    //...
}

It is evident that for numbers that are greater sqrt( 25 ) there will be a remainder. So there is no sense to continue the loop for divisors greater than sqrt( 25 ).

Pay attention that the loop is inefficient. You could initially check whether the given number is even and is not equal to 2. In this case it is obviousd that the number is not a prime number.

If the number is not even then you could apply a loop like

for ( int j = 3; j <= num / j; j += 2 )

Also if the number is equal to 1 then it is not a prime number.

score 0 · Answer 2 · answered Sep 21 '19 at 10:53

Lets think that you have number 100, and you need to find if it is prime or not. The number is prime if it can only be divided on 1 and on itself. So if we have 100, than on every number bigger than sqrt(100) (e.g. 10) that 100 can be divided the result will be in range from 1 to 10 (sqrt(100)). And as you don't need to find all divisors of number, but only one that is other than 1 and the number (in that way you can know if the number is not prime), so you are looping from 2 to sqrt(number)

Why do j need to be smaller or equal to sqrt(i)?

2 Answers2