Help with prime number program
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Thread: Help with prime number program

  1. #1
    Join Date
    Sep 2010
    Posts
    15

    Help with prime number program

    Beginner here, just want to clarify something.

    In an int/boolean function, regardless of where the first return value originates (e.g. from a loop), does the first value returned terminate the function (and the loop it is in, if it is in a loop) immediately?

    So an example, a program which tells you if a number is a prime number.
    Code:
    /* FUNCTION TO EVALUATE IF THE ARGUMENT IS A PRIME BETWEEN 1 AND 1000 */
    enum Logical {False, True};
    
    Logical small_prime(int integer)
    {  for (int factor = 2; factor<integer; factor++)
        {   
            if ( (integer % factor) == 0)
            return False;
        }
    
       return True;
    }
    Originally I was confused as I thought this function would return True no matter what happened in the for loop. The return true statement comes after it so I assumed after the loop finished it would read that (change false to true) and act accordingly. Now I realise this function only makes sense if the above deduction is true.

    Thanks
    KingG

  2. #2
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,127

    Re: Help with prime number program

    return is just that. It bails out of the function no matter what is going on.

  3. #3
    Join Date
    Jul 2009
    Location
    India
    Posts
    835

    Re: Help with prime number program

    Yes in your posted code it will turn False and exit. For more see msdn.

  4. #4
    Join Date
    Sep 2010
    Posts
    31

    Re: Help with prime number program

    By the way, first check if the number is dividable by 2, (if so - and it's not 2 itself, not a prime), then 5 (if so, and it's not 5 itself, not a prime). Start your loop at 3 and add 2 at every iteration (you already checked even numbers, didn't you?).

    If you think about using that function in a loop to check which numbers are primes in range say 1..1,000,000 - think again. You will be better off using Sieve of Eratosthenes, which is pretty elegant and easy way to generate primes, but will become memory hungry at bigger ranges:
    At range 1..10^9 vector<bool> will eat up ~123MB of RAM.

  5. #5
    Join Date
    Jun 2010
    Location
    Germany
    Posts
    2,591

    Re: Help with prime number program

    Quote Originally Posted by Xupicor View Post
    By the way, first check if the number is dividable by 2, (if so - and it's not 2 itself, not a prime), then 5 (if so, and it's not 5 itself, not a prime). Start your loop at 3 and add 2 at every iteration (you already checked even numbers, didn't you?).
    Basically a good idea to improve performace without taking too much effort. But why do you suggest to explicitly test for divisibility by 5? Wouldn't that get checked along with the other odd numbers?

    BTW, the Sieve algorithm is a pet of mine too.
    I was thrown out of college for cheating on the metaphysics exam; I looked into the soul of the boy sitting next to me.

    This is a snakeskin jacket! And for me it's a symbol of my individuality, and my belief... in personal freedom.

  6. #6
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,317

    Re: Help with prime number program

    Most importantly, limit the search to sqrt(N). If no number smaller than that can divide your number, none other will.
    Is your question related to IO?
    Read this C++ FAQ LITE article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

  7. #7
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,316

    Re: Help with prime number program

    Quote Originally Posted by monarch_dodra
    Most importantly, limit the search to sqrt(N). If no number smaller than that can divide your number, none other will.
    Remember to include the square root itself in the check.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  8. #8
    Join Date
    Jun 2010
    Location
    Germany
    Posts
    2,591

    Re: Help with prime number program

    Quote Originally Posted by monarch_dodra View Post
    Most importantly, limit the search to sqrt(N). If no number smaller than that can divide your number, none other will.
    Right. I had that in mind too but decided not to mention it to avoid making things too complicated. But while we're at it...

    1.) Of course the sqrt should be calculated before entering the loop and stored in a varibale because its calculation is expensive and it remains constant throughout the loop.

    2.) This will only really pay off if the function is called repeatedly in a loop itself, but calculation of the sqrt can be avoided entirely while maintaining the same most efficient point to exit the loop: In the loop, calculate not only the modulo but also the quotient. Once the quotient becomes <= the factor you have reached the sqrt and can terminate the loop. This is especially efficient in assembly language because the x86 DIV instruction provides both the modulo and the quotient at the same time. How much that gains in C++ depends on compiler optimizations but I'm confident that modern compilers can take advantage of that assembly instruction.

    I was thrown out of college for cheating on the metaphysics exam; I looked into the soul of the boy sitting next to me.

    This is a snakeskin jacket! And for me it's a symbol of my individuality, and my belief... in personal freedom.

  9. #9
    Join Date
    Sep 2010
    Posts
    31

    Re: Help with prime number program

    Yeah, how did I forget sqrt(n)? About that - you can actually generate primes (to a file, lets say, or just count'em) up to 10^18 with about 123MB RAM used if you mix your methods.
    The sieve gives you primes up to sqrt(10^18) == 10^9), and you loop through the rest of them, checking if they're dividable by any prime generated by the sieve. It will take some time though, especially if you will save those primes to a file.

    Quote Originally Posted by Eri523 View Post
    But why do you suggest to explicitly test for divisibility by 5? Wouldn't that get checked along with the other odd numbers?
    Primes are only odd numbers, right? But, there's no prime (other than 5 itself) with last digit being 5. So you can just go ahead and check it right there and then, with mod 5. If it's pretty high number, it'll save you few iterations. Although mod is pretty expensive on itself, so, you'd have to test it.

  10. #10
    Join Date
    Jun 2010
    Location
    Germany
    Posts
    2,591

    Re: Help with prime number program

    Ok, the x86 DIV instruction is relatively expensive (41 ticks in the 32-bit version on the P4 - that's what I have the manual for at hand) but that's still harmless compared to what it was on earlier CPUs where the division might even have been needed to be done in software (not on any x86 though, they always had the DIV instruction but it might have been less efficient).

    You can start setting up lots of these special cases if you want. IMO this would lead to a pretty complicated loop that rather would be counterproductive. Handling the special case of only checking odd divisors (except for 2 of course) is pretty simple and efficient and should be enough.

    Or you can use the Sieve algorithm: IMO, with a bit of imagination, this can be seen as a generic implementation of these special cases, even generating them dynamically.
    I was thrown out of college for cheating on the metaphysics exam; I looked into the soul of the boy sitting next to me.

    This is a snakeskin jacket! And for me it's a symbol of my individuality, and my belief... in personal freedom.

  11. #11
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,316

    Re: Help with prime number program

    Quote Originally Posted by Xupicor
    Primes are only odd numbers, right?
    You forgot about poor old 2 this time

    Quote Originally Posted by Xupicor
    But, there's no prime (other than 5 itself) with last digit being 5. So you can just go ahead and check it right there and then, with mod 5. If it's pretty high number, it'll save you few iterations.
    That might make sense, except that your instructions were to "start your loop at 3 and add 2 at every iteration". This means that the trial division by 5 would generally happen twice.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  12. #12
    Join Date
    Sep 2010
    Posts
    31

    Re: Help with prime number program

    Quote Originally Posted by laserlight View Post
    You forgot about poor old 2 this time
    Well, I don't see '2' on my keyboard, therefore there is no '2'. It's propaganda.


    Quote Originally Posted by laserlight View Post
    That might make sense, except that your instructions were to "start your loop at 3 and add 2 at every iteration". This means that the trial division by 5 would generally happen twice.
    Yup, you're right again. That actually didn't make much sense, did it? Well, that's a sign I need less coffee and more sleep. -_x Goodnight!

  13. #13
    Join Date
    Sep 2010
    Posts
    15

    Re: Help with prime number program

    Wow guys thanks a lot for the replies. Plenty of other stuff for me to research there!

    Just one question - how do you know how much memory your program uses? And is the memory being used always RAM yes?

  14. #14
    Join Date
    Jun 2010
    Location
    Germany
    Posts
    2,591

    Re: Help with prime number program

    The way to determine the amount of memory used by your program depends on the OS you run it on.

    For a simple console-type prime generator I would say it is likely that all the memory it uses actually is RAM. But depending on several factors, including the total memory your program uses, how long certain parts of that memory haven't been accessed and the overall memory load of the system, the probability may increase that parts of the memory used by your program get paged out to the hard drive. This process is transparent to your program, though.
    I was thrown out of college for cheating on the metaphysics exam; I looked into the soul of the boy sitting next to me.

    This is a snakeskin jacket! And for me it's a symbol of my individuality, and my belief... in personal freedom.

  15. #15
    Join Date
    Mar 2012
    Posts
    2

    Re: Help with prime number program

    for($j=0;$j<=50;$j++)//upto 50
    {
    $flag=true;
    for($i=2;$i<=($j/2);$i++)
    {
    if($j % $i == 0)
    $flag=false;
    }
    if($flag)echo $j.", ";
    }

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center