Please help me understand this

Question

4.00/5 (1 vote)

See more:

Hello guys, Im new to programming and just learning C++ from book by Brian Overland C++ without fear.I try to understand everything and i dont just read it.I try to understand all of it.I got to this part where we check if a number is a prime number.I really dont understand this part.

C++

i = 2
while (i <= sqrt(n))
{
    if (n % i == 0)
    is_prime = false;
    i++;
}

so, what i dont understand here is why do we check if i is lower than sqrt of n?I dont know why but i just cant understand this loop.I've seen more complicated programs and could understand more complicated loops, but i just cant understand this.Please if someone could just explain to me how it works.Sorry for my bad English.

Posted 26-Nov-15 9:04am

Dokara97

Updated 26-Nov-15 9:26am

Sergey Alexandrovich Kryukov

v4

Add a Solution

Comments

Afzaal Ahmad Zeeshan 26-Nov-15 16:05pm

Understanding programming or how a program works is not enough. When you are building a program, you need to know the algorithm too, Mathematics or similar subjects can cause a havoc sometimes.

Just like this program, you have no idea about i or the square root of n. If that is the case, look into the code block itself. You are going to divide n by i and then find out if the number is prime or not; do you know what prime numbers are?

The program is just the logic. That is defined by the Mathematical principles. C, C++, Java or C# programs are basically written on the standards of Mathematics, Physics or Statistics problems to explains how a language works.

Sergey Alexandrovich Kryukov 27-Nov-15 1:23am

Really nice advice, I appreciate it; you may also want to see mine in two comments below and to the Solution 1. :-)
Despite of apparent problems with the learning methods, I really appreciate the attitude of this inquirer.
—SA

Afzaal Ahmad Zeeshan 27-Nov-15 9:05am

Thank you for appreciation, but I can only see one comment below? Am I missing something? :-)

Sergey Alexandrovich Kryukov 27-Nov-15 17:36pm

One below and one in the comments to Solution 1.
—SA

[no name] 26-Nov-15 18:44pm

What you are doing is a good thing. Whenever you reach a block Google is there to help. What are primes and how to compute them? https://en.wikibooks.org/wiki/Some_Basic_and_Inefficient_Prime_Number_Generating_Algorithms

Sergey Alexandrovich Kryukov 27-Nov-15 1:21am

I really, really appreciate your attitude.

That's why I demonstrated for you how the code sample should be formatted by actually formatting it for you. Please, do yourself a favor, click "Improve question" and see how I formatted it, to know how to do it next time.

This is not old. Please see my comment to the Solution 1: it explains why your question is incorrect and what you would need to do to make it correct. Even though I immediately made a correct guess on what the code should do, it won't be the case, generally. The code sample should always be self-contained and the goal should be well explained.

Two comments above are also quite valuable, please pay close attention for them.

Good luck, call again.

—SA

[no name] 1-Dec-15 17:57pm

Thank you guys, i really appreciate this. I am new to this forum and programming by itself. I didnt want to skip this problem so i asked here.You explained to me very good.Problem is my main language is not English, so i find some problems like this very difficult to understand and in my main language there is no such good explanations on google like on English language.I asked my teacher about this and he helped me writing program like this but without sqr, but i guess this solutions are more effective and less wasteful.I will post it in solution.

3 solutions

Solution 4

C#

{
	int n;
	int ind = 0;
	int i = 2;
	cout<<"Type in number you want to check"<<endl;
	cin>>n;
	while(i<n)
	{
		if(n%i==0)
		ind++;
		i++;
	}
	if(ind==0)
	{
		cout<<"This is prime number"<<endl;
	}

		else
		{
		 cout<<"This is not prime number"<<endl;
	}

Posted 1-Dec-15 12:01pm

Dokara97

Updated 1-Dec-15 12:02pm

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

PIEBALDconsult · Accepted Answer · 2015-11-26T09:54:00

Solution 1

Because once you get to the square root, you have found all the possible factors (if any).
I take issue with that implementation though, because it will recalculate the square root on each cycle of the loop, and that's wasteful.

Posted 26-Nov-15 9:54am

PIEBALDconsult

Comments

Sergey Alexandrovich Kryukov 27-Nov-15 1:17am

That is an "incorrect answer" which deserves a 5.

It is "incorrect" only because an attempt to answer incorrect question is by definition formally incorrect, always. And the question is apparently incorrect, unless it is addressed to Brian Overland. The source code fragment is chosen in a wrong way, declarations and initializations of the values is not shown and the goal of the code is not explained. Obviously, in general case the code which compiles cannot be wrong or right: it can be wrong for one goal and right for another one.

—SA

PIEBALDconsult 27-Nov-15 10:01am

So what?

Sergey Alexandrovich Kryukov 27-Nov-15 17:35pm

Nothing. What "what" would you expect? Just sharing my opinion and explain my vote...
—SA

Member 10641779 · Accepted Answer · 2015-11-26T23:21:00

Solution 2

For example, take number 25. square root of 25 is 5. So any number between 6 to 24 will not divide 25. so no need run loop for these extra numbers.

Suppose here n=19, square root of 19 is 4.35889894 or 4 as integer.
loop will run i=2,3,4.(only 3 times). otherwise you need to run it from 2 to 18 that is clearly wastage of time.

C#

i = 2
while (i <= sqrt(n))
{
    if (n % i == 0){
        is_prime = false;
        break;           // break the loop if number is not prime.
    }
    i++;
}

So by using sqrt(n) you can make your program execute faster.

Posted 26-Nov-15 23:21pm

Member 10641779

Updated 29-Nov-15 18:37pm

v6

Comments

PIEBALDconsult 27-Nov-15 10:02am

Try 16 now.

Member 10641779 30-Nov-15 0:36am

As square root of 16 is 4. that means loop will run from 2 to 4. In first if condition if(16 % 2 == 0) it will return true. is_prime will be false and then break the loop. Result 16 is not a prime number.

PIEBALDconsult 30-Nov-15 17:54pm

Yes, yet there is a factor within the range of 5 to 16.

Member 10641779 1-Dec-15 5:22am

The thing I want to explain is that if a number is not completely divisible by any number less than its square root. it will not be completely divisible by any number greater then its square root(except itself).

Member 10641779 1-Dec-15 5:24am

for example take a number 17. its square root will be 4.123 or 4. if 17 is not divisible by 2,3 and 4. it will not be divisible by 5,6,7...16.