[oclug] Re: code wars 2.0

[Taavi Burns]

My obfuscated entry.  It does run a twiddle bit slower than the fast,
non-obfuscated one for some reason.
It's almost identical to my non-obfuscated one, except shorter.  ;)

The main body is <450 characters.  The whole file is just 599 bytes.

Normally I wouldn't attach, but it's just so _small_!  ;)  (even
non-obfuscated!)

My slow solution is O(n^2).  The fast one is O(n^1.5), explaining why it
is so much faster in the long run.  It's hard to tell in the short run,
'cause the program is done in less than .01s for n = 1000.  I'm pretty
sure that the time cost of the newer algorithm is O(n), so it doesn't
matter much anyway.  Besides.  If speed is an issue,  with RAM prices the
way they are, just use a lookup table.

Unless you're in an embedded application, in which case you hire a
mathematician.  ;)

Taavi Burns
Pleas Czech yore dock yew meant fur errs...
...Andy ooze pill cheque!
/*eof*/
-------------- next part --------------
/*
** primes.c - A prime number generator
**
** Taavi Burns, August 2001
** tburns at ualberta.ca
*/

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

int main(int a,char**v){ char*l="+-------------------------\
---+",*f="|%11d%16d |\n";int*p,i,c,x,g,s,t;if(a!=2){printf(
"Usage:\n\t%s <COUNT>\n\n",**v);return 1;}sscanf(v[1],"%d",&
a);p=malloc(a*sizeof(int));*p=2;i=1;s=*p**p;t=1;puts(l);pri\
ntf("|      Count%16s |\n","Prime");puts(l);printf(f,1,*p);
for(c=*p+1;i<a;g=1){for(x=0;x<t;x++){if(c%p[x]==0){g=0;brea\
k;}}if(g){p[i++]=c;printf(f,i,c);}c++;c++;if(c>=s){s=p[t]*p[
t++];}}puts(l);return 0;}

/*eof*/
-------------- next part --------------
/*
** primes.c - A prime number generator that seeds itself
**
** Taavi Burns, August 2001
** tburns at ualberta.ca
*/

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

void find_x_primes(long num_primes)
{
	long *primes;
	int primes_index;
	long count;
	long x;
	char junk[256];
	int primeflag;
	primes = malloc(num_primes * sizeof(long));
	primes[0]=2;
	primes_index = 1;
	for (count = primes[0] + 1;primes_index < num_primes, primeflag=1;) {
		for (x = 0; x < primes_index; x++) {
			if (count%primes[x] == 0) {
				primeflag = 0;
				break;
			}
		}
		if (primeflag) {
			primes[primes_index++] = count;
		}
		count++;
		count++;
		if (primes_index == num_primes) break;
	}
	printf("+----------------------------+\n");
	printf("|      Count           Prime |\n");
	printf("+----------------------------+\n");
	for (x = 0; x < primes_index; x++) {
		printf("|%11d%16d |\n", x+1, primes[x]);
	}
	printf("+----------------------------+\n");
}

int main(int argc, char *argv[])
{
	if (argc != 2) {
		printf("Usage:\n\tprimes <COUNT>\n\n");
		return 1;
	}
	sscanf(argv[1], "%d", &argc);
	find_x_primes(argc);
}
/*eof*/