Some logic with prime-numbers

This is a discussion on Some logic with prime-numbers within the C++ Programming forums, part of the General Programming Boards category; Well...Sorry to ask a really stupid or noob question. But I have been noticing that whenever we try to test ...

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    65

    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.

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    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...

  4. #4
    Registered User
    Join Date
    Sep 2008
    Posts
    65
    Quote Originally Posted by matsp View Post
    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.

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,415
    So, what do you find confusing?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User
    Join Date
    Sep 2008
    Posts
    65
    Quote Originally Posted by laserlight View Post
    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?

  7. #7
    chococoder
    Join Date
    Nov 2004
    Posts
    515
    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.

  8. #8
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    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.

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by EVOEx View Post
    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.
    But that assumes that we're learning about functions, and not just simple loops, right?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  10. #10
    Registered User
    Join Date
    Oct 2008
    Posts
    1,262
    Quote Originally Posted by matsp View Post
    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?

  11. #11
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    Quote Originally Posted by EVOEx View Post
    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
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  12. #12
    Registered User
    Join Date
    Sep 2008
    Posts
    65
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Finding Prime Numbers
    By dan724 in forum C Programming
    Replies: 11
    Last Post: 12-14-2008, 11:12 AM
  2. Prime Numbers
    By EdSquareCat in forum C++ Programming
    Replies: 9
    Last Post: 05-29-2007, 05:54 PM
  3. Prime Numbers and Array...
    By Deux in forum C Programming
    Replies: 12
    Last Post: 12-20-2004, 03:12 PM
  4. prime numbers code compile error
    By Tony654321 in forum C Programming
    Replies: 5
    Last Post: 10-10-2004, 10:13 AM
  5. prime numbers
    By Unregistered in forum C Programming
    Replies: 17
    Last Post: 08-20-2002, 08:57 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21