Thread: Prime Numbers

Originally Posted by Salem

So why don't you have two functions?
- isPrimeNumber(n)
- findLowestDivisor(n)

Please don't, that's horribly inefficient. Because, probably, you need to find the lowest divisor to find out whether the number is a prime number. Probably, there should be one function, findLowestDivisor, which returns 0 (or whatever) when the number is prime.

But I agree, the code is a (buggy) mess.

Couldn't you just do:

if n == 1 return (true); // is prime
else
int n = 2;
while(n <= sqrt(number))
if(number % n == 0) return n; // return the divisor
n++;

return 0; // return 0 if the number is not prime

n == 1 doesn't need an else, since it would have the return statement.

The while loop seems simple and clear. For larger number, I'd add a little logic to optimize it.

I forgot to add, I can only use the standard input output library <stdio.h>. sqrt(number) requires <math.h> or at least won't work with stdio.h.

Since some seem to find it hard to read, could anyone suggest a better format? It would help me alot...

thanks

Code:

#include <stdio.h>
#include <stdlib.h>

unsigned int low_d(unsigned int x)
{
        unsigned int i;

        for (i = 2; i < x; i++){
                if (!(x % i)){
                        return i;
                }
        }
        return 1;
}

int main(void)
{
        unsigned int i;

        for (i = 0; i <= 0xffffffff; i++){
                if (low_d(i) == 1){
                        printf("%i\n", i);
                }
        }
        return 0;
}

Like this, maybe?

EDIT: Sorry, just got bored and was curious how long it would take to run. . . It's been about 3 hours and we're in the millions.

Originally Posted by Elysia

How is splitting code into several functions inefficient?

The "usual" method for finding out whether an integer is a prime number is to test all divisors (from low to high) until it finds one. If you split the test whether it is a prime and finding the lowest divisor into two functions, you'd have to do something like this:

Code:

if(!isPrime(n))
  printf("%d\n", getLowestDivisor(n));

But isPrime already calculates what getLowestDivisor must know and must probably recalculate. So I would prefer:

Code:

int divisor = getLowestDivisor(n);
if(divisor)
  printf("%d\n", divisor);

Of course, isPrime might cache the lowest divisor for the function getLowestDivisor. This can be done in two ways: it could store it in a map with lowest divisors. That's doable, even though it still adds a O(log m) complexity (where m is the size of the cache) that we shouldn't have. It could also just cache the lowest divisor of the last call to isPrime. That would work in this case, but once we extend the application to test two numbers at the same time, it won't.

Originally Posted by Elysia

I see what you're getting at. But it's still essentially two tasks: one is finding the lowest divisor and one finding if it's a prime or not. So you could break it into two functions.
You could use a common function, such as GetLowestDivisor, to combine these functions and return the lowest divisor. I see you didn't mean what I thought you meant, though. What you said came off as "making two functions out of one is inefficient"

Well, theoretically it IS less efficient... Pushing the parameters, calling... Pfew, that's gotta be at least 3 clock cycles ;-). (Actually, I bet it's a bit more, but still very little)

I understand your design choice according to the idea that separate tasks should have different functions. However, you should also avoid repetitive code, and getLowestDivisor and isPrime would share most of their code. I'm not saying you wouldn't solve this properly, though, but how would you do it?

I'd build two functions. getLowestDivisor, to get the lowest divisor (obviously) or 0 if there is no divisor. Then I would build:

Code:

bool isPrime(int n)
{
  return getLowestDivisor(n) == 0;
}

No repetitive code, but two tasks split over two functions. However, the task specified here would probably only use getLowestDivisor.

How would you do it - out of interest, even though I expect pretty much the same... I can't see any better way to do this.

Originally Posted by EVOEx

Code:

bool isPrime(int n)
{
  return getLowestDivisor(n) == 0;
}

Isn't that two functions? Isn't that almost exactly what I put up there? Is there an echo in this thread?