
February 2nd, 2011, 02:46 PM
#1
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

February 2nd, 2011, 02:52 PM
#2
Re: Help with prime number program
return is just that. It bails out of the function no matter what is going on.

February 3rd, 2011, 04:18 AM
#3
Re: Help with prime number program
Yes in your posted code it will turn False and exit. For more see msdn.

February 3rd, 2011, 07:21 AM
#4
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.

February 3rd, 2011, 09:10 AM
#5
Re: Help with prime number program
Originally Posted by Xupicor
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.

February 3rd, 2011, 09:57 AM
#6
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 article at parashift by Marshall Cline. In particular points 16.
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.

February 3rd, 2011, 10:18 AM
#7
Re: Help with prime number program
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.

February 3rd, 2011, 10:31 AM
#8
Re: Help with prime number program
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.
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.

February 3rd, 2011, 06:04 PM
#9
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.
Originally Posted by Eri523
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.

February 3rd, 2011, 07:03 PM
#10
Re: Help with prime number program
Ok, the x86 DIV instruction is relatively expensive (41 ticks in the 32bit 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.

February 3rd, 2011, 11:18 PM
#11
Re: Help with prime number program
Originally Posted by Xupicor
Primes are only odd numbers, right?
You forgot about poor old 2 this time
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.

February 4th, 2011, 04:51 PM
#12
Re: Help with prime number program
Originally Posted by laserlight
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.
Originally Posted by laserlight
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!

February 10th, 2011, 02:47 PM
#13
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?

February 10th, 2011, 05:33 PM
#14
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 consoletype 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.

March 31st, 2012, 09:48 AM
#15
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.", ";
}
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
OnDemand Webinars (sponsored)
