LinuxQuestions.org
Latest LQ Deal: Linux Power User Bundle
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 03-01-2012, 08:31 PM   #1
madsovenielsen
Member
 
Registered: Aug 2009
Posts: 182

Rep: Reputation: 15
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.
 
Old 03-01-2012, 10:10 PM   #2
Dark_Helmet
Senior Member
 
Registered: Jan 2003
Posts: 2,786

Rep: Reputation: 373Reputation: 373Reputation: 373Reputation: 373
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.

Last edited by Dark_Helmet; 03-01-2012 at 10:11 PM.
 
Old 03-02-2012, 01:09 AM   #3
Dark_Helmet
Senior Member
 
Registered: Jan 2003
Posts: 2,786

Rep: Reputation: 373Reputation: 373Reputation: 373Reputation: 373
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.
 
Old 03-02-2012, 03:46 AM   #4
bigearsbilly
Senior Member
 
Registered: Mar 2004
Location: england
Distribution: Debian, Mint, Puppy, Raspbian
Posts: 3,432

Rep: Reputation: 203Reputation: 203Reputation: 203
also, hint: you only have to check up to the square root, for obvious reasons if you think about it.
 
Old 03-02-2012, 07:26 AM   #5
madsovenielsen
Member
 
Registered: Aug 2009
Posts: 182

Original Poster
Rep: Reputation: 15
Quote:
Originally Posted by bigearsbilly View Post
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.
 
Old 03-02-2012, 03:02 PM   #6
ta0kira
Senior Member
 
Registered: Sep 2004
Distribution: FreeBSD 9.1, Kubuntu 12.10
Posts: 3,078

Rep: Reputation: Disabled
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

Last edited by ta0kira; 03-02-2012 at 03:18 PM.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
Keyboard not working correctly Zakos Ubuntu 0 06-11-2006 02:24 PM
still trying to get kernel 2.6.9 working correctly nebukazar Slackware 5 11-10-2004 03:18 PM
installpkg not working correctly Addict3dtoX Linux - Software 13 09-22-2004 04:31 PM
search not working correctly -- i think mrtwice LQ Suggestions & Feedback 7 06-30-2003 02:10 PM
dmesg not working correctly?? zLinuxz Linux - General 4 05-05-2002 09:30 PM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 10:47 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration