3 Replies - 8000 Views - Last Post: 17 October 2007 - 09:56 PM Rate Topic: -----

#1 mrskinnyarms   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 17-October 07

Help With Sieve of Eratosthenes program

Posted 17 October 2007 - 01:30 PM

So...
No matter how I try, it seems like I can't get primearray to filter all of it's unmarked nonzero values into intarray or for array to dive into sieve() and retain any of the changes (it seems it's filled with every 4th value from zero in main()).

Help would be much appreciated.

 
 #include <stdio.h>
 #include <stdlib.h>
 
/*prototype*/

void sieve(int *, int *, int *);

int main(void)
{		
	int numprimes = 0;
	int size = 100;
	int *array = NULL;
	int i = 0;
	
	sieve(&size, &numprimes, array);

	printf("\n%d\n\n", numprimes);
	
	for(i = 0; i < numprimes; i++)
		printf("%d ", &array[i]); 
	 
	return 0;
}


void sieve(int *size, int *numprimes, int *array)
{
	int *intarray = (int *) malloc(*size * sizeof(int));
	int *primearray = NULL;
	int i = 0, j = 0;
	int primecounter = 0;
	
	for(i = 0; i < *size; i++)
		intarray[i] = i;
		
	/* at positions where there are multiples of i, mark as zero */
  for( i = 2; i * i < *size; i++ )
	if( intarray[i] )
	  for( j = i + i; j < *size; j += i )
		intarray[j] = 0;

	  /* count all values that haven't been marked */
  for( j = 2; j < *size; j++ )
	if(intarray[j])
	  primecounter++;
  
  primearray = (int *) malloc(primecounter + 1 * sizeof(int));
  
  for(i = 0; i < primecounter; i++)
		primearray[i] = i;
  
   /* store all prime numbers from intarray into primearray */
  for( j = 2; j < *size; j++ )
	if(intarray[j])
	  primearray[j] = j;
	  
  array = primearray;
	  
  for(i = 0; i < *size; i++)
		printf("%d ", intarray[i]); printf("\n");	 
	  
  for(i = 0; i < primecounter; i++)
		printf("%d ", primearray[i]);	
	  
  *numprimes = primecounter;
  
  array = &intarray[0];
  
  free(intarray);
  free(primearray);
}
 

This post has been edited by mrskinnyarms: 17 October 2007 - 01:32 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Help With Sieve of Eratosthenes program

#2 NickDMax   User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2255
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Help With Sieve of Eratosthenes program

Posted 17 October 2007 - 09:06 PM

Well I am still looking it over, but I did notice that you did not deal with returning your array correctly. You pass a pointer to an array, so far so good, except that you pass a value of NULL... So you are not passing a variable "by reference" rather you are passing... well a null pointer.

(I am having a hard time thinking of exactly how to explain this)

Ok, when you pass a function a pointer, you are passing it the location of where data is stored (or will be stored). So if you wanted the argument "array" argument to pass back from the function a pointer to an array then you need to make the argument a "pointer to a pointer" -- that is, a pointer to the location of the address referenced by the pointer "array" (in the main function).

Remember that the arguments to a function are lost: they are one way, they go into the function, but don't come back out (they are pushed on the stack when the function is called, and then popped off the stack when the function exits). So to use arguments to pass information back to the calling code, you need to "cheat" by passing a pointer to the value you want to populate with data. Then you can use this pointer to edit the data at that location (which the calling function can see). -- BUT the arguments themselves are transient -- they live on the stack and are lost at the end of the function (just as all local variables).

So if you wanted to return an array (using a "by reference") method you will need to pass a pointer-to-a-pointer:

void func (int size, int **array) {
	//array = a pointer 
   //*array is also a pointer so if *array = &intarray[0]
   //then the calling function will have access to intarray[]
   //providing that you don't "free" the array!
  *array = (int *)malloc(size * sizeof(int));
}

void someFunc () {
	int *theArray;
	func(100, &theArray);
	//theArray points to an array of 100 integers.
	free(theArray); //have to free the array AFTER IT IS USED
}


I will continue to look over you code and see if I can spot your 0 bug.
Was This Post Helpful? 0
  • +
  • -

#3 NickDMax   User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2255
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Help With Sieve of Eratosthenes program

Posted 17 October 2007 - 09:34 PM

Another point:

primearray = (int *) malloc(primecounter + 1 * sizeof(int));

take a close look at the formula used to calculate the array size!

primecounter + 1 * sizeof(int) == primecounter + sizeof(int)

I think you meant:

primearray = (int *) malloc((primecounter + 1) * sizeof(int));
Was This Post Helpful? 0
  • +
  • -

#4 NickDMax   User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2255
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Help With Sieve of Eratosthenes program

Posted 17 October 2007 - 09:56 PM

Well I worked my way though the code... there were a number of small errors, here is some working code:
#include <stdlib.h>

//prototype

void sieve(int *, int *, int **);

int main(void)
{		
	int numprimes = 0;
	int size = 100;
	int *array = NULL;
	int i = 0;
	
	sieve(&size, &numprimes, &array);

	printf("\n%d\n\n", numprimes);
	
	for(i = 0; i < numprimes; i++) {
	   printf("%d ", array[i]);
	}

	
	return 0;
}


//Note that we are passing all values "by referance"
void sieve(int *size, int *numprimes, int **array)
{
	//Allocate a workspace
	int *intarray = (int *) malloc(*size * sizeof(int));
	
	//Used to point to an array of results
	int *primearray;
	
	//counters
	int i = 0, j = 0;
	
	//counter to calculate number of primes
	int primeCounter = 0;
	
	
	//initialize workspace
	for(i = 0; i < *size; i++) { intarray[i] = i; }
		
	//Sieve of Eratosthenes:
	// at positions where there are multiples of i, mark as zero 
	for( i = 2; i * i < *size; i++ ) {
		if( intarray[i] ) {
			for( j = i + i; j < *size; j += i ) {
				intarray[j] = 0;
			}
		}
	}

	
	//Count up the number of primes found
	for( i = 1; i < *size; i++ ) {
		if(intarray[i]) { 
			primeCounter++;
		}
	}
  
	//Setup an array to hold primes (note that there are primeCounter # of primes)
	primearray = (int *) malloc(primeCounter * sizeof(int));
  
	//Fill out primearray with all primes found
	j = 0;
	for(i = 0; i < *size && j < primeCounter; i++) { 
		if (intarray[i]) {
			primearray[j++] = i;
		}

	}
  
	//Print out the found primes from intarray
	for(i = 0; i < *size; i++) {
		if (intarray[i]) printf("%d ", intarray[i]); 
	}
	  
	printf("\n");

	//Print out the primes in prime array
	for(i = 0; i < primeCounter; i++) {
		printf("%d ", primearray[i]);
	}
 
	printf("\n");

	//Ensure we are passing back the number of primes
	*numprimes = primeCounter;
  
	*array = primearray;
 
	//we are done with intarray and it can be freed to the heap
	free(intarray);
	
	//We don't want to free this memory until we are done with it!!!
	//free(primearray);
}


Your problem logic was correct, your understanding of pointers was not -- the code above uses your logic to find the primes, but corrects the errors using the pointers.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1