Algorithm Help

[54616E6E6572]

Part of the project I'm working on involves finding prime numbers, and am stuck on removing 2 of the goto statements from my code. Any help would be appreciated.

Code: Select all

int* FindXPrimes(int x)
{
	int* p = malloc(x * 4);
	p[0] = 2;
	int n = 3;
	int j = 0;
	P2:
		p[++j] = n;
		if(j == x)
			return p;
	P4:
		n += 2;
		int k = 1;
	while(true)
	{
		int q = n / p[k];
		int r = n % p[k];
		if(r == 0)
			goto P4;
		if(q <= p[k])
			goto P2;
		k++;
	}
}

[~]

What about "duplicating" the initialization code? I don't see anything wrong with that, and it will only increase the code size by some bytes in exchange of having a code independent of goto's, macros or subroutines:

Code: Select all

int* FindXPrimes(int x)
{
   int* p = malloc(x * 4);
   p[0] = 2;
   int n = 3;
   int j = 0;
   P2:
      p[++j] = n;
      if(j == x)
         return p;
   P4:
      n += 2;
      int k = 1;
   while(true)
   {
      int q = n / p[k];
      int r = n % p[k];
      if(r == 0)
      {
//         goto P4;
       n += 2;
       k = 1;
       continue;
      }
      if(q <= p[k])
      {
//         goto P2;
       p[++j] = n;
       if(j == x)
          return p;
      }
      k++;
   }
}

[gravaera]

I didn't really try to read the code as such, but I have a hashed out pseudocode solution:

Code: Select all

int n_is_prime(int n)
{
   if (!n%2) { return 0;};
   for (int i=0; i<n/2; i++)
   {
      if (!n/i) {return 0;};
   };
   return 1;
};

If you need to search through an array, all it would take is a for loop that calls that function on each element. It seems like your code is supposed to find all of the prime numbers from 1 to x. Well you could also use that snippet for that, too: go for loop, 1 - x, and apply the function to each element. If it returns trues, append it to your array. (The one you're allocating dynamically).

[NickJohnson]

I didn't really try to read the code as such, but I have a hashed out pseudocode solution:

Code: Select all

int n_is_prime(int n)
{
   if (!n%2) { return 0;};
   for (int i=0; i<n/2; i++)
   {
      if (!n/i) {return 0;};
   };
   return 1;
};

If you need to search through an array, all it would take is a for loop that calls that function on each element. It seems like your code is supposed to find all of the prime numbers from 1 to x. Well you could also use that snippet for that, too: go for loop, 1 - x, and apply the function to each element. If it returns trues, append it to your array. (The one you're allocating dynamically).

I agree - I think the only way to make a concise prime number generator is to have a function within it, because of the multiple points at which the inner loop can break, and with different results. If you keep it in one function, you must use either an extra variable or a goto. And who knows, maybe a prime number checker will also be useful in whatever you're doing, especially if you are already working with primes.

[Brendan]

Hi,

Any help would be appreciated.

If the maximum number of primes you need is small then use a lookup table (e.g. "unsigned int lookupTable[] = {2, 3, 5, 7, 11, 13, ..., whatever_the_highest_needed_prime_is};"). If the maximum number of primes you need is large, then use a Sieve of Eratosthenes where one bit represents every odd number (and split the processing up into blocks that are about half the size of the CPU's cache). For example, if the CPU's cache is 4 MiB then you'd work on 2 MiB blocks, where each 2 MiB block contains 16777216 odd numbers (e.g. from 1 to 33554431 for the first block, from 33554433 to 67108863 for the second block, etc).


Cheers,

Brendan

[stephenj]

What do you expect x to be most of the time? Max(x)? Min(x)?

There are different strategies to find primes. For most cases I deal with, I'm partial to the sieve of atkin.