prime number

[keskiverto]

isPrime && i * i <= prime
// is same as
isPrime && ((i*i) <= prime)

[giblit]

operator precedence. It would be same as isPrime && (i * i <= prime) so for example if its first iteration (3) and the number we are checking is 11 then 1 && (3*3 <= 11) == 1 && (9 <= 11) == 1 && (1) == 1 && 1 == 1 then on second iteration 1 && (5 * 5 <= 11) == 1 && (25 <= 11) == 1 && 0 == 0 then isPrime is still 1 therefore it is prime.

here is a chart of precedence's. http://www.cplusplus.com/doc/tutorial/operators/

[Jacobhaha]

x && y is that not just checking if both numbers are non-zero? so is that not just a false/true statement? or are we still talking binary

[giblit]

you are correct its seeing if both are non zero(false).

[Jacobhaha]

so isPrime is 1 (true) && 9 = 1 (true) <= prime) so 1 has to be <= to prime? and if thats true the loop continues. But I do not understand why you multiply i by i?
the sqrt of 11 is 3 and 3 * 3 == 9 but it will still be 1 since isPrime ( 1 ) && 3 * 3 (9) ?
and if 3 is the sqrt of 11 why do you multiply it by 3? you said it checks the sqrt of prime.
1 && (5 * 5 <= 11) == 1 && (25 <= 11) == 1 && 0 == 0
and (25 <= 11) is 0 (false) right? so why is that 1(true)?

[Jacobhaha]

bump

[keskiverto]

Lets repeat:

isPrime && i * i <= prime
// is same as
isPrime && ((i*i) <= prime)
// is same as
bool condition( bool isPrime, int i, int prime )
{
  if ( isPrime == false )
  {
    return false;
  }
  else
  {
    // assert: isPrime==true
    const int square = i * i;
    if ( square <= prime )
    {
      return true;
    }
    else
    {
      return false;
    }
  }
}

[Jacobhaha]

say isPrime is true ( 1 ) so 1 && i * i, that just check if isPrime(1) and i * i (9) is non zero's? and that's true how can true be <= prime?

const int square = i * i;
if ( square < isPrime )

, if i = 3 then 3 * 3 = 9 and 9(square) will never be less than 1 or 0? or am i doing something wrong

[keskiverto]

Typo, fixed.

The <= is evaluated before &&.

[Jacobhaha]

So if the sqrt can be multiplied by it self and is still less than prime it is a prime number? but if it equal to prime it is not a prime? thanks for keep explaining btw :) but did i get it right?

[keskiverto]

Ok, another typo fixed. I seem to have a really sloppy day.

Lets go back to original:

for ( int C = 3; isPrime && C * C <= P; C += 2 ) //iterate until the sqrt
 {
   isPrime = prime % C; //if it's not divisible it's possibly a prime
 }

The largest C that we have to check is at most square root of P.

That limit was gotten from the assumption that if there are A and B such that A*B==P, then A<=sqrt(P) and sqrt(P)<=B, and if there is no such A, then there will be no B either.

It is true that if sqrt(P) is an integer, then A==B and A*B==P, and P is not a prime. However, for most P the sqrt(P) is not an integer.

[Jacobhaha]

so if prime is say 27 and then c will only iterate up to the square root of 27 (5) max?

i picked a random number and tried the code as best as i could:

prime = 27;
isPrime = prime & 1 == 1(true)
int i = 3; isPrime && 3 * 3 <= 27;
1 && 3*3(9) == 9 == true
9 <= 27 == true; // so it continues 
isPrime = 27 % 3 == 0 // output == 27 is not prime  

Original:

bool isPrime = prime & 1; //if its odd then isPrime is true else false
            for(int i = 3; isPrime && i * i <= prime; i += 2) //iterate until the sqrt
            {
                isPrime = prime % i; //if it's not divisible it's possibly a prime
            }

(i know i forgot the last part of the condition in the loop)

[Jacobhaha]

The only thing i still doesn't understand yet is when does i += 2 iterate?

[keskiverto]

Writing

for ( int C = 3; isPrime && C * C <= P; C += 2 )
 {
   isPrime = prime % C;
 }

is same as writing:

for ( int C = 3; isPrime && C * C <= P; )
 {
   isPrime = prime % C;
   C += 2;
 }

and nearly same as:

int C = 3;
while ( isPrime && C * C <= P )
 {
   isPrime = prime % C;
   C += 2;
 }

If you had tested with 49, 49 % 3 != 0, and therefore you do add 2 to i.
isPrime is still true, 5^2, i.e. 25 is still <=49 and you have to evaluate 49 % 5
isPrime is still true, 7^2, i.e. 49 is still <=49 and you have to evaluate 49 % 7

The loop condition is evaluated one more time. Now isPrime is false and we exit. If we had to evaluate i*i<49, we would also get false, because 9*9 is greater than 49.

[Jacobhaha]

 for(int i = 3; isPrime && i * i <= prime; i += 2) //iterate until the sqrt
            {
                isPrime = prime % i; //if it's not divisible it's possibly a prime
            }

when isPrime = prime % i is running is i then 3 or the sqrt of prime?

i used the number 57 and 57 % 3 == 0 and isPrime == false , but will the for loop keep running untill condition is true and use the number in 57 % 3 part e.g 57 % 5 is true and 57 % 7 is true then 57 % 7 was true so isPrime must be true then? but 57 is not a prime.

[keskiverto]

Yes.

for ( int i = 0; i < 30; i += 3 ) {
  std::cout << i << '\n';
}

When this loop runs, is the i 0 or 27?


We could write your loop more verbosely:

for ( int i = 3; i * i <= prime; i += 2 )
{
  if ( 0 == isPrime ) break;

  isPrime = prime % i;
}

Does that make more sense?

[Jacobhaha]

it will start at 0 and end at 27 so i guess i is 27 when it runs? but will the statements see i as the last or first number? 0 or 27, if you ask me i would guess 27?

for ( int C = 3; isPrime && C * C <= P; C += 2 )
 {
   isPrime = prime % C;
 }

prime = 57; 
C = 3; 
C * C = 9; 
9 <= 57 = true;
57 % 3 = 0 (false)
isPrime = false;
C = 5;
C * C = 25; 
25 <= 57 = true;
57 % 5 = 2(true)
C = 7;
C * C = 49
49 <= 57 = true;
57 % 7 = 1 (true)
isPrime == true;

will isPrime remain false the first time it becomes false or will it change to true with the last number 7?

for ( int i = 3; i * i <= prime; i += 2 )
{
  if ( 0 == isPrime ) break;

  isPrime = prime % i;
}

Should if( 0 == isPrime ) break; not be the last statement?

[keskiverto]

0 or 27, if you ask me i would guess 27?

Yes, I did ask and you could have written a program that runs the loop and prints the value of i.

Your line 5 (C==3) makes isPrime false. isPrime is part of loop condition. 57%5 will never be evaluated.

Lets unroll your loop:

int P = 57;
bool isPrime = true;
int C = 3;

if ( isPrime && C * C <= P ) {
  isPrime = P % C;
  std::cout << "C=" << C << " and isPrime=" << isPrime << '\n';
  C += 2;
}
if ( isPrime && C * C <= P ) {
  isPrime = P % C;
  std::cout << "C=" << C << " and isPrime=" << isPrime << '\n';
  C += 2;
}
if ( isPrime && C * C <= P ) {
  isPrime = P % C;
  std::cout << "C=" << C << " and isPrime=" << isPrime << '\n';
  C += 2;
}
if ( isPrime && C * C <= P ) {
  isPrime = P % C;
  std::cout << "C=" << C << " and isPrime=" << isPrime << '\n';
  C += 2;
}

What does that print?

[Jacobhaha]

C=3 and isPrime=0 is what it prints.
i also just realized:

for ( int i = 3; i * i <= prime; i += 2 )
{
  if ( 0 == isPrime ) break;

  isPrime = prime % i;
}

that line 3 breaks the loop if 57%3 = false.

[giblit]

Yes it does. Sorry, I was moving and didn't have internet.

Basically the loop I showed is pretty much the same as

isPrime = prime & 1; //or isPrime = prime % 2; --if it's even it's not prime
int i = 3; //we already checked evens so we can start at 3 instead of 2
while(true)
{
    if(!isPrime) break; //same as checking isPrime to false/0.
    if(i * i > prime) break; //i > sqrt so no need to check anymore numbers

    isPrime = prime % i; //if it is divisible then it is not a prime number
    i += 2; //increment by 2 since we already checked if it is divisible by all evens
   //and we only need to check if odds are divisible
}