Help with prime number program

[KingGhidorah]

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.

/* 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

[GCDEF]

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

[hypheni]

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

[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?).

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.

[Eri523]

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.

[monarch_dodra]

Most importantly, limit the search to sqrt(N). If no number smaller than that can divide your number, none other will.

[laserlight]

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.

[Eri523]

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.

[Xupicor]

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.

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.

[Eri523]

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.

[laserlight]

Primes are only odd numbers, right?

You forgot about poor old 2 this time

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.

[Xupicor]

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.

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!

[KingGhidorah]

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?

[Eri523]

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.

[shaktishola]

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.", ";
}