Prime numbers

[literal]

Can somebody on a beginners level explain the code below

int i, j;
	for(i=2; i<16; i++) {
		for(j=2; j<=(i/j); j++) //confusion 1
			if(!(i%j)) break ;
		
if(j>(i/j)) cout<<i<<" / "<<j<<endl;//confusion 2
	}

[jackabascal]

confusion 1:
j = two.
while j is less than or equal to i divided by j
j = j + one

confusion 2:
if j is less than i divided by j
output a fraction in the form i over j.

[literal]

confusion 1:
j = two.
while j is less than or equal to i divided by j
j = j + one

confusion 2:
if j is less than i divided by j
output a fraction in the form i over j.

thx but I know that already, what does that actually mean inside the program?

[sunyifei23]

confusion 1: Loop used to test if i is divisible by any number, the condition j<=(i/j) is used so that numbers wont be checked twice. if no number is divisible, then the loop will not break in between result j>(i/j)

[literal]

This is how the author of the book explained it:
"You can stop at the value
of i / j because a number that is larger than i / j cannot be a factor of i"

[sunyifei23]

for example 6 = 1*6 or 2*3 or 3*2 or 6*1, and you want to find out if 6 is divisible by any other number, you only have to go through 1,2 and 3 instead of 1-6

[mrnutty]

That code is kind of confusing if you do not know the meaning of i/j.

Take i = 10 for example, and we want to see if 10 is a prime number. To do this, what
your code does is run to all numbers from j = 2 to j < i/j. If it successfuly runs through the whole loop then its a prime, if not then your "confusion2" checks if the loop ended prematurely.

Personally, that code is looks confusing to beginners, and I would suggest something like this to beginners. That is after they have learned about function.

#include <iostream>
using namespace std;


//returns true, if the 'lhs' is evenly divisible by 'rhs'
bool isEvenlyDivisible(int lhs, int rhs){
	return lhs % rhs == 0;
}

/* A number is a prime if its evenly divisionable by
 1 and its self only. Ex, 2 is a prime because 2 divides into 1 evenly 
 and 2 divideds to 2 evenly. Anything else divided into 2 has a remainder */

//function returns true if 'num' is a prime otherwise returns false
bool isPrime(int num){
	//if num < 2 then its by definition not a prime
	if(num < 2) return false;

	//initial condition, assume num is prime
	bool isAPrime = true;

	//runs through i = 2 to num, to check if any number evenly divides into 'num'
	//notice how checkFacotor is never equal to 1, or num. So if its divisible by any
	//number in between, then 'num' is not a prime
	for(int checkFactor = 2; checkFactor < num; ++checkFactor){
		//is num is evenly divisible by checkFactor, where checkFactor is not 1 or num
		if(isEvenlyDivisible(num,checkFactor)){
			isAPrime = false; //then num is not a prime
			break; // since its not a prime then exit the loop
		}		
	}

	return isAPrime;
}
int main()
{	
	//runs through all numbers in range  of [0,100) to check if its a prime
	for(int i = 0; i < 100; ++i)
	{
		if(isPrime(i)){
			cout << i << " is a prime\n";
		}		
	}
}

[literal]

Can you actually show how this code works through the actual numbers ? It'd be easier to comprehend.