input: | A list of prime numbers in increasing order entered in the command tail |
output: |
A stream of integers, each having at least one of the given prime numbers as a factor and only prime numbers from the given list of primes as factors. The integers are placed in the output stream in increasing order. |
limits: |
Since the stream is infinite and computer resources are bounded, not all of the stream can be constructed. However, the code below makes no attempt at determining when a resource bound is reached. |
hamming(p,T) = if (p == NULL) return(NULL); else return(car(p)*T + merge(hamming(p,car(p)*T),hamming(cdr(p),T)))
#include < stdio.h > #define ADD 1 #define POP 2 long a[1000][4],head = 1,tail = 0; /********************************************************************** * * queue: < ADD > X < state-array > -> suspends process & stores state-array * < POP > X < state-array > -> resume process of least "value" * (state-array is output) * **********************************************************************/ long queue(int func, long q[]) { long tptr, i, val_arg, ptr_arg, t_arg; val_arg = q[1]; ptr_arg = q[2]; t_arg = q[3]; if (func == ADD) { tptr = ++tail; while (a[tptr-1][1] > val_arg && tptr > head) { for (i=1; i<=3; i++) a[tptr][i] = a[tptr-1][i]; tptr -= 1; } a[tptr][3] = t_arg; a[tptr][2] = ptr_arg; a[tptr][1] = val_arg; } else if (func == POP) { q[1] = a[head][1]; q[2] = a[head][2]; q[3] = a[head][3]; head++; } } long ham(long p[]) { long right[4], left[4], q[4], i; int fbreak(); right[1]=0; right[2]=0; right[3]=0; left[1]=0; left[2]=0; left[3]=0; q[1]=p[1]; q[2]=1; q[3]=1; queue(ADD,q); while (1) { queue(POP,q); printf("%d ", q[1]); if (getchar() == 27) exit(0); left[1]=q[3]*p[q[2]+1]; left[2]=q[2]+1; left[3]=q[3]; right[1]=q[3]*p[q[2]]*p[q[2]]; right[2]=q[2]; right[3]=q[3]*p[q[2]]; queue(ADD ,right); if (left[1]>0) queue(ADD ,left); } } main(int argc, char **argv) { long p[11], i; printf("\nprime list:"); p[argc] = 0; for ( i = 1 ; i < argc ; i++ ) { p[i] = atoi(argv[i]); printf(" %d", p[i]); } printf("\n\n"); ham(p); }