LinuxQuestions.org

LinuxQuestions.org (/questions/)
-   Programming (https://www.linuxquestions.org/questions/programming-9/)
-   -   C algorithm not working correctly. (https://www.linuxquestions.org/questions/programming-9/c-algorithm-not-working-correctly-932257/)

madsovenielsen 03-01-2012 08:31 PM

C algorithm not working correctly.
 
Hello

I have made a prime number algorithm, its working very well on integers under 1 billion.

At first i did not use malloc() to allocate the space nessesary for the divisors array, i was doing it directly with the int variable n. This dident work on large integers, and the program made a stackdump.

Code:

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

int prime(int n) {

    int x;
    int i;
    float result;
    /*int divisors[n];*/

    int *divisors = (int *) malloc(n * sizeof (int));

    if(divisors == NULL) {
        return -1;
    }

    for(i = 0; i < 1; i++) {
        for(x = 2; x < n; x++) {

            divisors[i] = x;
            result = (float) n / x;

            if(result == (int)result) {
                return 0;
                free(divisors);
            }
        }
    }
    free(divisors);
    return 1;
}

int main(int argc, char *argv[]) {
    if(prime(1000000007) == 1) {
        printf("Prime");
    } else {
        printf("Not prime");
    }

}

The above program, using malloc() can now handle much larger input, but when the number gets big enough, like 1000000007, the prime() function returns 0 and the program "Not prime" although 1000000007 is a proven prime.

Any help is greatly appreciated.

Dark_Helmet 03-01-2012 10:10 PM

Quote:

Originally Posted by madsovenielsen
Code:

int *divisors = (int *) malloc(n * sizeof (int));

You do realize that the above code will request 4 * 1000000007 bytes of memory, correct? Or rather, 93% of 4 gigabytes.

My guess would be that the memory allocation is failing. You say that prime() is returning 0, but you do not have any code that verifies this. The message "Not prime" is displayed whenever prime() returns anything but 1. If memory allocation fails, it returns -1, which will lead to the same "Not prime" message being displayed as if 0 had been returned.

Dark_Helmet 03-02-2012 01:09 AM

It's been a while since my prior reply. What I'm going to add, I'd rather make sure it's seen and not potentially missed (because an edit would not send a "new reply" email).

Three things (that you did not ask for), but that I want to make sure you are aware of.

#1) You have a memory leak.
Code:

if(result == (int)result) {
  return 0;
  free(divisors);
}

Your program leaves the prime() function immediately upon evaluating a return statement. Therefore, the free() call listed after the return will never execute. Your program will fail to release reserved memory every time you discover a non-prime number.

#2) You do not need to do the memory allocation at all. Your prime() function can simply use a single integer that you increment repeatedly. For example:
Code:

int prime(int n) {
  int x;
  int quotient;

  for( x = 2; x < n; x++ ) {
    quotient = n / x;
    if( quotient * x == n )
      return 0;
  }

  return 1;
}

#3) The numeric data types have limits on the values they contain. A normal int variable uses 32 bits to store a number. And because an int may be positive or negative, an int variable may contain a value (base 10) between [+2,147,483,647, -2,147,483,648].

If you want your program to process higher values than those, consider using
unsigned int (range: [+4,294,967,295, 0])
long int (range: [+9,223,372,036,854,775,807, -9,223,372,036,854,775,808])
unsigned long int (range: [+18,446,744,073,709,551,615, 0])

Though, if you do use the greater-range variable types, I strongly encourage you to experiment with creating some alternate method of determining a prime than by your current increment-divide approach.

bigearsbilly 03-02-2012 03:46 AM

also, hint: you only have to check up to the square root, for obvious reasons if you think about it.

madsovenielsen 03-02-2012 07:26 AM

Quote:

Originally Posted by bigearsbilly (Post 4616676)
also, hint: you only have to check up to the square root, for obvious reasons if you think about it.

That is correct, there is also no point in doing calculations on numbers not ending in: 1, 3, 7, or 9.

Thanks for the help, bigearsbilly and Dark_Helmet.

ta0kira 03-02-2012 03:02 PM

Since you're using single-precision numbers (i.e. float,) your algorithm becomes unreliable for values > 8388608 (the width of the "fraction" component is 23 bits,) which could easily give you a false-positive for having a factor of 1000000007. You should use % instead of / and eliminate numbers if the result is zero (i.e. skip the floating-point.)
Kevin Barry


All times are GMT -5. The time now is 05:38 AM.