Frobenius numbers: Difference between revisions
Add C
Not a robot (talk | contribs) (Add APL) |
Not a robot (talk | contribs) (Add C) |
||
Line 151:
freevec(primes)
$)</lang>
{{out}}
<pre>1
7
23
59
119
191
287
395
615
839
1079
1439
1679
1931
2391
3015
3479
3959
4619
5039
5615
6395
7215
8447
9599</pre>
=={{header|C}}==
<lang c>#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define LIMIT 10000
/* Generate primes up to N */
unsigned int sieve(unsigned int n, unsigned int **list) {
unsigned char *sieve = calloc(n+1, 1);
unsigned int i, j, max = 0;
for (i = 2; i*i <= n; i++)
if (!sieve[i])
for (j = i+i; j <= n; j += i)
sieve[j] = 1;
for (i = 2; i <= n; i++) max += !sieve[i];
*list = malloc(max * sizeof(unsigned int));
for (i = 0, j = 2; j <= n; j++)
if (!sieve[j]) (*list)[i++] = j;
free(sieve);
return i;
}
/* Frobenius number */
unsigned int frob(unsigned const int *primes, unsigned int n) {
return primes[n] * primes[n+1] - primes[n] - primes[n+1];
}
int main() {
/* Same trick as in BCPL example. frob(n) < primes(n+1)^2,
so we need primes up to sqrt(limit)+1. */
unsigned int *primes;
unsigned int amount = sieve(sqrt(LIMIT)+1, &primes);
unsigned int i;
for (i=0; i<amount-1; i++) printf("%d\n", frob(primes, i));
free(primes);
return 0;
}</lang>
{{out}}
<pre>1
| |||