Thread: Some logic with prime-numbers

Well...Sorry to ask a really stupid or noob question. But I have been noticing that whenever we try to test the prime-ness, we always have to do things like Type A_Variable = true;, and this has to be put at the beginning of the program before we start anything else. Why do we always have to do that? Is there another way around do deal with prime number? Can it be put inside the loop or anywhere that doesn't effect the code that's being written?

That's what baffles me a lot as a noob.

I don't really get what you mean. 2-3 programs that dealt with prime numbers that I have seen didn't require anything like that. But again I am not really an expert on the field. If you want post an example...

Originally Posted by matsp

That's obviously a little bit depending on what you are ACTUALLY trying to do, but if we assume that you are trying to prove that a particular number is a prime, then the normal way is to prove that it ISN'T a prime, and by setting a variable "isprime = true" at the beginning, and then looping until we either have tested all possible divisors, or we have found one that divides the number into another whole number and then setting "isprime" to false, is a reasonable approach.

We can of course use many other ways to indicate that we have found a value that we can divide by. We could use the method of setting "divisor = 0", and then if we find something we can divide the number by, we set "divisor" to the current number we divide it by. When the loop is done, we check if divisor is zero - if so, it's a prime. If not, it's not a prime.

The key point is that whenever we have a case where we try to find something (or find OUT IF something), it's often a good way to make an assumption, and then prove the opposite. In computing, it's often easier to prove the presence of something, rather than the absence, so we assume that a number is a prime (isprime = true), then prove that it's not by proving the presence of a divisor (e.g. 35 can be divided by 5 [and 7]).

--
Mats

Take my last post for an example...This is the example done by the author of Brian Overland, who was a leader of programming project of Microsoft for 10 years and now a CEO.

Code:

#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;
}

Well...This is what I have noticed...The author include the int type data and use it as a bool type...And it is assumed to be true until proven otherwise...And I have seen other examples, which were done the same way.

Originally Posted by laserlight

So, what do you find confusing?

The is_prime? Why does it have to be placed outside of the while loop? Is it possible to include it inside the while loop?

So when you use bool type, you always have to assume things to be true until it is proven to be false?

if you placed it inside the loop the value would be reset with each iteration, you don't want that.
And no, you can use negative logic as well, starting from the assumption that something is false and setting it to true only when you're certain of the fact.
But in this case that's rather harder to do, as it's very easy to determine whether some number is not prime but you won't know whether it's prime until you've handled all potential candidate numbers it might be divided by.

Honestly, I think the code is quite bad. Honestly, did that make it into a book? No wonder many people can't code properly... If this is a book you're reading, I think it's better to pick up another one (unless the rest doesn't suck this badly, I don't know about that).

Anyway, enough flaming. I would like to actually add something. In my opinion, a lot more readable solution would be to get rid of the variable and put the entire check-primeness routine in a function that would simply return false as soon as it knew something isn't prime.
It would also be a lot faster than this, although you could easily fix that by adding a single break.

Originally Posted by matsp

But that assumes that we're learning about functions, and not just simple loops, right?

--
Mats

True. But that would make the example wrong in my opinion. You shouldn't write a bad program as example just because you haven't learned everything yet. You should write a small program that makes correct use of the correct things. This loop is obviously a for-loop converted into a while loop. But should it just use a while loop because one may not know about for-loops yet? Or should you just present a better example?

Besides, isn't it more logical to cover function calls before actually calling one - like sqrt - and before casting?

Originally Posted by EVOEx

Honestly, I think the code is quite bad. Honestly, did that make it into a book? No wonder many people can't code properly... If this is a book you're reading, I think it's better to pick up another one (unless the rest doesn't suck this badly, I don't know about that).

Anyway, enough flaming. I would like to actually add something. In my opinion, a lot more readable solution would be to get rid of the variable and put the entire check-primeness routine in a function that would simply return false as soon as it knew something isn't prime.
It would also be a lot faster than this, although you could easily fix that by adding a single break.

Production code makes bad examples, examples make bad production code. They have different purposes. Producton code is designed to be straight forward, work with possibly pre-existing code, and follow constraints that may not be readily apparent from examining the code. Example code is designed to teach a method or function and illustrate its use in as simple and easy to understand a manner as possible.

the typical test for primnes loop is

Code:

bool is_prime = true; // assume its prime until proven false
 
while(is_prime){
   //check for divisors
   // if a divisor is found set is_prime to false
   // if we have checked all possible divisors, break;
   } // at this point if the number is found to be composite or the range is finished, the loop will exit
 
// at this point is_prime states whether the tested number is prime or composite

Well...This is the book recommended by this website, which is "C++ without fear" by Brian Overland. The language he used for writing this book is easy to understand and unlike those books out there with a lot of grammatical English and sometimes use quite a lot of jargons without telling you what they are. But THIS BOOK is, I sometimes, find is kind of confusing. They tell you something but doesn't really give you the exact instruction or enough examples for easier understanding. Besides, the functions the author talks about even confuses me more without enough info.

But according to this author profolio, he worked for Microsoft for 25 years, 10 years as a leader for all existed projects. And now he has become a CEO.