Prime Numbers

I'm busy with a code that should determine whether a certain value is a prime number or not. If the number isn't prime, it should determine the smallest divisor of that value. Unfortunately, I'm having problems getting this to work..

Code:

---

#include <stdio.h>

int main()
{
    int input;/*input variable*/
    int i=1; /*used to loop the user input (user should enter an integer greater than '1'*/
    int div=0;/*used to determine the smallest divisor of the input value if it is not prime*/
    int n=3;/*used in formula to check odd numbers for prime.*/
    char rept;/*option to repeat program*/
   
    do
    {
        do
        {
          input=i;
     
          printf("\nType a number >1: ");
          scanf("%d", &input);//integer input point
          getchar();//buffer filter
          i++;
          }
        while(i<=1);
   
          printf("\nYou entered %d.\n", input);
   
        if(input%2==0)
        {
          div+=i;//sum to determine the smallest divisor, if the input value is even (not prime)
          printf("\n%d is the smallest divisor of %d!\n", div, input);
          }
        else if(input%2==1)
        {
          n=input/n+1;//sum to determine which odd integers are not prime
          div+=n-1;//if the input is odd and is NOT prime, this sum determines the smallest divisor

          if(n%2==0)
          printf("\n%d is the smallest divisor of %d!\n", div, input);
       
          else if(n%2==1)
          printf("%d is a prime number!\n", input);
          }
        printf("Would you like to try again (y/n)? ");
        scanf("%c", &rept);//option to repeat the program...
        getchar();//buffer filter
    }
    while(rept=='y'||rept=='Y');
    return 0;     
}

---

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

It would
a) make the code more readable
b) allow you to test both functions separately

Which would then enable you to say to us things like
"findLowestDivisor() isn't working for odd numbers"

Quote:

---

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.

Quote:

---

Originally Posted by SilentPirate007

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

---

Well you could iterate until number/2 instead of sqrt(number) if you are not allowed to use math.h . However, keep in mind this is less efficient. For example if number = 121 with sqrt(number) you would iterate until you reach 11 and conclude that 11 divides 121. with number/2 you are iterating 5 times more numbers.

Quote:

---

Originally Posted by EVOEx

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.

---

How is splitting code into several functions inefficient?

Quote:

---

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.

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" :)

Quote:

---

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.

Well, meh, not sure what the lowest divisor actually is and I'd have to dig up my old find prime numbers code.
But you know that the compiler will likely optimize that function call so no harm ;)

Quote:

---

Originally Posted by claudiu

Well you could iterate until number/2 instead of sqrt(number) if you are not allowed to use math.h . However, keep in mind this is less efficient. For example if number = 121 with sqrt(number) you would iterate until you reach 11 and conclude that 11 divides 121. with number/2 you are iterating 5 times more numbers.

---

Or he could simply iterate up until sqrt(x) by doing it like this:

Code:

---

for (i = 2; i*i < x; i++)]

---

Quote:

---

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?

Quote:

---

Originally Posted by Kennedy

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

---

As I said, in this case the isPrime function wouldn't even be used. Sometimes, in a project that would grow, I would actually add it even if I don't use it directly just for completeness and future extension (as long as it's not too much work).
However, in this case, I'd leave out the function completely. So no, in THIS case it would be one function. In GENERAL case it would be two.