sqrt with while loop

[kenryuakuma]

#include <iostream>
#include <math.h>

using namespace std;

int main()
{
    // Declare four variables n, i, an, and is_prime respectively.
    int n;        // Number to test for primeness
    int i;        // Loop counter
    int is_prime;

    // Assuming that the number is prime until proven otherwise
    is_prime = true;

    // Prompt user input
    cout << "Please enter a number for the primeness number test: ";
    cin >> n;

    // Test for prime-ness by checking for divisibility
    // by all whole numbers from 2 to sqrt(n)
    i = 2;
    while(i <= sqrt(static_cast<double>(n))){
        if(n % i == 0){
            is_prime = false;
        }    
            i++;
    }

    if(is_prime){
        cout << "The number is prime." << endl;
    }else{
        cout << "The number is not prime.";
    }

    return 0;
}

2.4.1 Optimize the program further by calculating the square root of n just once rather than over and over as was done in the example. To perform this optimization, you will need to declare another variable and set it to the square root of n. The type should be double. Write a complete program that includes this optimization.

How do you optimize it? I am clueless...I need some help here. But it would be favorable if somebody could provide an example with explanation in great details and that might help a noob a lot.

[helios]

Uh... The description is pretty clear.

To perform this optimization, you will need to declare another variable and set it to the square root of n.

.
Here's another speed up: add && is_prime to the while condition. it will save you some cycles.

[Bazzy]

To perform this optimization, you will need to declare another variable and set it to the square root of n. The type should be double

double sqrtn = sqrt( n );

Optimize the program further by calculating the square root of n just once rather than over and over as was done in the example

while(i <= sqrtn )

[guestgulkan]

This loop is wrong !

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

[kenryuakuma]

Oh my bad! For Helios, how can I add && is_prime to the while loop?

For Bazzy, is it possible to give me a complete code for the exercise with comments as the explanation for the exercise?

[kenryuakuma]

#include <iostream>
#include <math.h>

using namespace std;

int main()
{
    // Declare four variables n, i, an, and is_prime respectively.
    int n;        // Number to test for primeness
    int i;        // Loop counter
    int is_prime;

    // Assuming that the number is prime until proven otherwise
    is_prime = true;

    // Prompt user input
    cout << "Please enter a number for the primeness number test: ";
    cin >> n;

    // Test for prime-ness by checking for divisibility
    // by all whole numbers from 2 to sqrt(n)
    i = 2;
    double sqrtn = sqrt(static_cast<double>(n));
    while(i <= sqrtn && is_prime){
        if(n % i == 0){
            is_prime = false;
        }
            i++;
    }

    if(is_prime){
        cout << "The number is prime." << endl;
    }else{
        cout << "The number is not prime.\n";
    }
    system("pause");
    return 0;
}

Again here is my code with help of Bazzy and helios.

[helios]

The condition of being prime is "primality", not "primeness".

[firedraco]

Gotta love English XP

Anyway...I noticed this...

int is_prime;

    // Assuming that the number is prime until proven otherwise
    is_prime = true;

Did you mean bool is_prime;?

[kenryuakuma]

Yes bool is_prime is what I meant and we could substitute bool type with int type. Is my code correct and is done as requested according to the question of the exercise? Well! For helios, yes, primality is correct but "prime-ness" is the word written by the author as well as the example was written by him.

[anders43]

all even numbers except '2' are not prime numbers
odd numbers could be primes

so you could start instead by first dividing by 2, then after that 3,5,7,... up to your sqrt(n)

i.e. i++ could be replaced with i+=2 instead to speed up things

[kenryuakuma]

Well...Did I do the exercise correctly as the QUESTION of the EXERCISE requests? It seems that the sqrt of n only loops once, not twice. This is what confuses me and I am just wondering how is it done?