Help with Prime Factorization Program

[GreyHat64]

I'm working on Project Euler as a coding exercise. The third problem asks what the greatest prime factor of a large arbitrary number is. Here's my code:

/* ANSI C program to compute the greatest prime factor of CONSTANT. Primes up to the * sqrt of CONSTANT are found using the sieve of Eratosthenes. Primes are then * used for trial division in descending order to find the greatest prime * factor. */#include <stdio.h>#include <stdlib.h>#include <math.h>#define CONSTANT 600851475143.0int main(void){	enum boolean { FALSE, TRUE };	long sqrtConstant = floor(sqrt(CONSTANT));	char *sieve = malloc((sqrtConstant+1) * sizeof(char)); /* Boolean array */	double *primes = malloc(sizeof(double)); /* Primes up to sqrt of const */	double *temp;	int i = 0; /* Greatest index of primes */	long n;	if (sieve == NULL || primes == NULL) {		printf("Error allocating memory!\n");		return 1;	}/*	if (sieve == NULL) {		printf("Error allocating memory! (sieve)\n");		return 1;	}	if (primes == NULL) {		printf("Error allocating memory! (primes)\n");		return 1;	}*/	for (n = 0; n <= sqrtConstant; n++) { /* Initialize the sieve */		if (n < 2) {			sieve[n] = FALSE;		} else {			sieve[n] = TRUE;		}	}	for (n = 2; n <= sqrtConstant; n++) { /* Sieve of Eratosthenes */		if ((sieve[n] = TRUE)) {			long m;			for (m = n * n; m <= sqrtConstant; m += n) {				sieve[m] = FALSE;			}		}	}	for (n = 0; n <= sqrtConstant; n++) { /* Convert sieve to array of primes */		if ((sieve[n] = TRUE)) { /* Segfault */			primes[i] = n;			temp = realloc(primes, ((i++)+2) * sizeof(double));			if (temp !=NULL) {				primes = temp;			} else {				free(primes);				printf("Error allocating memory!\n");				return 1;			}		free(sieve);		free(temp);		}	}	while (primes[n] != floor(primes[n])) { /* Determine greatest prime factor*/		i--;	}	printf("%.f\n", primes[i]);	free(primes);	return 0;}

I'm getting segfaults of all different sorts from my sieve array. Initially I was getting a stack overflow because the sieve was an array stored in the stack. It shouldn't have caused a stack overflow on my machine though, because it's only 775,147 bytes in size, smaller than my 8 MB stack limit. Either way, I decided to move the sieve into the heap by using a pointer instead of an array. Since then, I've been dealing with access and write related segfaults with the sieve. I can't figure out what the underlying issue is. Also, general criticism of my code would be appreciated.

[Ciccioo]

you missed a multiplication here, hence the segmentation faults [another edit: nevermind, i didn't see how it was handled later]

	double *primes = malloc(sizeof(double)); /* Primes up to sqrt of const */

also, here

	for (n = 0; n <= sqrtConstant; n++) { /* Convert sieve to array of primes */		if ((sieve[n] = TRUE)) { /* Segfault */			primes[i] = n;			temp = realloc(primes, ((i++)+2) * sizeof(double));			if (temp !=NULL) {				primes = temp;			} else {				free(primes);				printf("Error allocating memory!\n");				return 1;			}		free(sieve);		free(temp);		}	}

you free sieve while you're actually still using it

it should be freed at the end, with primes, i believe

 

edit:

regarding the program itself, it's a good program to find all the prime factors of a given number, but you just need the bigger factor

wouldn't it be enough to just iterate through all the numbers from sqrtConstant down and stop when you find a factor?

 

edit again:

	long sqrtConstant = floor(sqrt(CONSTANT));

try to print out sizeof(long), i think it's usually the same as int

for working with big numbers, you want a long long, that's the biggest integer type provided by the standard

actually, unsigned long long would be even better

[Avratz]

 

 

You also have a leak if your realloc fails. You need to free everything before the return.

[GreyHat64]

you missed a multiplication here, hence the segmentation faults [another edit: nevermind, i didn't see how it was handled later]

-snip-

also, here

-snip-

you free sieve while you're actually still using it

it should be freed at the end, with primes, i believe

 

edit:

regarding the program itself, it's a good program to find all the prime factors of a given number, but you just need the bigger factor

wouldn't it be enough to just iterate through all the numbers from sqrtConstant down and stop when you find a factor?

 

edit again:

-snip-

try to print out sizeof(long), i think it's usually the same as int

for working with big numbers, you want a long long, that's the biggest integer type provided by the standard

actually, unsigned long long would be even better

Thanks for pointing out the misplaced free statements. That was part of the issue. Just to address your other points:

1. There is no multiplication in the initialization of *primes because it is used as a dynamically growing array later in the code.

2. I can't just iterate down from sqrtConstant because that could give me composite factors that would have to be factored, creating some nasty recursion.

3. I used a long for sqrtConstant because it's guaranteed to be a 32-bit signed integer, while an int could be either 16-bit or 32-bit. 16-bits would be too small for sqrtConstant.

 

-snip-

You also have a leak if your realloc fails. You need to free everything before the return.

Noted and fixed. Thanks!

Now here's the new code:

I'm getting a segfault at my while loop that determines the greatest prime factor. Any ideas on this one?

/* Program to compute the greatest prime factor of CONSTANT. Primes up to the * sqrt of CONSTANT are found using the sieve of Eratosthenes. Primes are then * used for trial division in descending order to find the greatest prime * factor. */#include <stdio.h>#include <stdlib.h>#include <math.h>#define CONSTANT 600851475143.0int main(void){	enum boolean { FALSE, TRUE };	long sqrtConstant = floor(sqrt(CONSTANT));	char *sieve = malloc((sqrtConstant+1) * sizeof(char)); /* Boolean array */	double *primes = malloc(sizeof(double)); /* Primes up to sqrt of const */	double *temp;	int i = 0; /* Greatest index of primes */	long n;	if (sieve == NULL || primes == NULL) {		printf("Error allocating memory!\n");		return 1;	}/*	if (sieve == NULL) {		printf("Error allocating memory! (sieve)\n");		return 1;	}	if (primes == NULL) {		printf("Error allocating memory! (primes)\n");		return 1;	}*/	for (n = 0; n <= sqrtConstant; n++) { /* Initialize the sieve */		if (n < 2) {			sieve[n] = FALSE;		} else {			sieve[n] = TRUE;		}	}	for (n = 2; n <= sqrtConstant; n++) { /* Sieve of Eratosthenes */		if (sieve[n] == TRUE) {			long m;			for (m = n * n; m <= sqrtConstant; m += n) {				sieve[m] = FALSE;			}		}	}	for (n = 0; n <= sqrtConstant; n++) { /* Convert sieve to array of primes */		if (sieve[n] == TRUE) {			primes[i] = n;			temp = realloc(primes, ((i++)+2) * sizeof(double));			if (temp !=NULL) {				primes = temp;			} else {				free(sieve);				free(primes);				printf("Error allocating memory!\n");				return 1;			}		}	}	free(temp);	free(sieve);	while (primes[i-1] != floor(primes[i-1])) { /* Determine greatest prime factor*/ /*segfault*/		i--;	}	printf("%.f\n", primes[i]);	free(primes);	return 0;}

[Avratz]

temp and primes point to the same memory. You don't want to free it before your loop.

 

 

 

The debugger is your friend 

[GreyHat64]

Thanks again. All of my segfaults are fixed now, but the code is still not quite working. I'll be investigating it further from this point. This may be a stupid question, but what IDE or debugger is that? I've been using GDB and Valgrind.

[Avratz]

http://www.codeblocks.org/

 

Few things: 

 

1) You don't need doubles. Use long or long long

 

2) Look at your while loop

 

 

I made some tweaks, and it works 

[WanderingFool]

So I will make a note on a problem in your code which is probably a biggy, and then I will comment on the writing on the code.

 

Problem

The biggest issue at the moment is that you are using if(sieve[n] = TRUE).  Use == not =, otherwise the if statement will always be true or false (In theory the compiler could choose TRUE to be 0 at which point it would be always false...but it will most likely choose 1).

 

Also

while (primes[n] != floor(primes[n]))

primes is constructed from ints...so this will effectively always be true, this is an even bigger issue when you include the fact that you are using i-- in the loop so this will be an infinite loop...oh and also this will cause a crash as well before the infinite loop because n is actually 1 larger than your array (I think so anyways).

This isn't a problem, but I just wanted to point this out before I comment on the code portion itself because this relates to your primes array.  You are using double's and as others have suggested you should be using long or long long's....although since you are using a sieve this is also pointless...you are restricted to the the range of integers.  This is because you are only allocating memory up to integer size...which means you can only have integer max elements, so the max value can't be higher than that.  (Although if you compile under 64 bit you could address more memory and thus increase the size to 2^64...at which point use long)

 

Comments on the code itself

In general I would say you are writing clean looking code, so it is fairly easy to find the errors.  I also applaud you for using ANSI-C, it can be very helpful to learn it.  Now for the analysis of your code....since this is prime numbers I would put an emphasis on better optimizations, it appears that you have a few loops that you really don't need at all (with a few tweaks to your code).

 

So first I am going to point out this main for loop, which I think is consuming way to much resources for basically no new information.

	for (n = 0; n <= sqrtConstant; n++) { /* Convert sieve to array of primes */		if ((sieve[n] = TRUE)) { /* Segfault */			primes[i] = n;			temp = realloc(primes, ((i++)+2) * sizeof(double));			if (temp !=NULL) {				primes = temp;			} else {				free(primes);				printf("Error allocating memory!\n");				return 1;			}		free(sieve);		free(temp);		}	}

The thing that I ask myself is, what is the purpose of this loop?  You are effectively trying copying the sieve into primes, just to later figure out if that prime is the largest divisor of the solution.  I would make the argument that at each point when sieve[n] is true, you will have a prime number n.  This would mean that by reversing through the list you will pull out the biggest primes first, and thus you should just be checking whether the factor exists at that time rather than just saving the prime and doing the check later on.

 

What I am saying is that loop can be combined with the intention of your while loop to form this.

	for (n = sqrtConstant; n >= 2; n--) { /* Going from biggest to smallest so I can exit when a divisor is found */		if ((sieve[n] == TRUE)) { /* Segfault */ /* Added the == instead of = */                        if(CONSTANT % n == 0) /* Using mod to check divisiblity */                                break; /* Breaking out, this will mean that n will equal the largest prime number that is divisible */		}	}       /* Now n will equal the highest prime number, but if n == 1 that means there wasn't a factor and thus constant was a prime */       if(n == 1)              printf("There was no divisors");        else              printf("%d", n);

It simplifies your code, and makes it more efficient.

 

 

 

Also as a note, I believe enum would actually slow down your code (vs using 1 and 0 as bytes)...because if I am not mistaken most compilers actually put enum's as integers (unless told otherwise...I forget the command line option for gcc though).  Anyways that is just a note, nothing too big.  Although as an extra thought concept, your for loop of initializing is very inefficient...you could even use memset and just manually set the first 2 to false....or better yet, you could assume 1 is false and 0 is true (this would require changing your code and not using the enum, or just setting their variables if you must).  If 1 is false and 0 is true you could just start each for loop at 2 (as 0 and 1 are pointless anyways), then you could just use calloc instead of malloc....calloc zeros out the memory (very quickly I might add).  This would just shave off a few seconds on very large numbers though.

[Ciccioo]

(i like how my post is vastly more stupid than @WanderingFool 's and @Avratz 's but still nailed the "best answer" thing. in yo face! i'm embarassed by that)

[WanderingFool]

(i like how my post is vastly more stupid than @WanderingFool 's and @Avratz 's but still nailed the "best answer" thing. in yo face! i'm embarassed by that)

lol, that was the best laugh in a long time.  In all seriousness though I thought you had answered the question correctly as well initially, I only figured out the bigger issues when I read his code a bit more carefully to critique it

[Ciccioo]

lol, that was the best laugh in a long time.  In all seriousness though I thought you had answered the question correctly as well initially, I only figured out the bigger issues when I read his code a bit more carefully to critique it

yep i didn't notice the equals error either, also because it had the double brackets that are usually used to explicitely say "hey, i really meant to use the assignation operator rather than the equals operator"

i think that error came from a correction to the code made just to make a compilation warning go away, that warning like "add a pair of brackets for assignation used as truth value"

[XtremeTechGaming]

(i like how my post is vastly more stupid than @WanderingFool 's and @Avratz 's but still nailed the "best answer" thing. in yo face! i'm embarassed by that)

I only liked that post because of your profile picture!

[Geldar]

http://en.wikipedia.org/wiki/Primality_test

 

Use a primality test, far faster than brute force factorisation

[WanderingFool]

http://en.wikipedia.org/wiki/Primality_test

 

Use a primality test, far faster than brute force factorisation

From my understanding though, you can't get the greatest factor from most primality tests, which is the main goal of GreyHat64