algorithm by eratosthenos

[Joe Smith]

It is nothing short of embarrassing to feel the need to ask for help on
this. I can't see how I would make the main control for this. What I want
is a for loop and a test condition. And while I know, from things I
pondered 2 decades ago, that a fella can write code without a goto, I'm
stuck.

/* sieve1.c */

#define whatever 20
#define N whatever
#include <stdio.h>

int main(void)
{
int i, A[N+1], m, sum;

/* initialize to 0 */

for (i = 0; i <= N; ++ i) A[i] = 0;

/* output */
printf("Primes less than N are:\n");
for (i = 2; i <= N; ++ i)
{
if (A[i] == 0)
printf("%d

[Fred Kleinschmidt]

"Joe Smith" <gr**********@n etzero.net> wrote in message
news:44******** *************** @news.usenetmon ster.com...

It is nothing short of embarrassing to feel the need to ask for help on
this. I can't see how I would make the main control for this. What I
want
is a for loop and a test condition. And while I know, from things I
pondered 2 decades ago, that a fella can write code without a goto, I'm
stuck.

/* sieve1.c */

#define whatever 20
#define N whatever
#include <stdio.h>

int main(void)
{
int i, A[N+1], m, sum;

/* initialize to 0 */

for (i = 0; i <= N; ++ i) A[i] = 0;

/* output */
printf("Primes less than N are:\n");
for (i = 2; i <= N; ++ i)
{
if (A[i] == 0)
printf("%d

In a Sieve of Eratosthenos, the first step is to fill the array with
all of the consecutive integers, not to zero out the array.
Next, set A[i]=0 for any A[i] divisible by 2
Next, starting at the first non-zero element after 2,
set to zero all items divisible by that number.
Repeat until you get to the end of the array.
This can be done without ever performing a divide!

Doesn't need any go-to or test to jump out.
Probably is cleaner to use a while-loop instead of a for-loop.
index = 2;
while ( index < N ) {
/* fill in the rest of the code*/
}

--
Fred L. Kleinschmidt
Boeing Associate Technical Fellow
Technical Architect, Software Reuse Project

[mensanator]

Fred Kleinschmidt wrote:

"Joe Smith" <gr**********@n etzero.net> wrote in message
news:44******** *************** @news.usenetmon ster.com...

It is nothing short of embarrassing to feel the need to ask for help on
this. I can't see how I would make the main control for this. What I
want
is a for loop and a test condition. And while I know, from things I
pondered 2 decades ago, that a fella can write code without a goto, I'm
stuck.

/* sieve1.c */

#define whatever 20
#define N whatever
#include <stdio.h>

int main(void)
{
int i, A[N+1], m, sum;

/* initialize to 0 */

for (i = 0; i <= N; ++ i) A[i] = 0;

/* output */
printf("Primes less than N are:\n");
for (i = 2; i <= N; ++ i)
{
if (A[i] == 0)
printf("%d
In a Sieve of Eratosthenos, the first step is to fill the array with
all of the consecutive integers, not to zero out the array.
Next, set A[i]=0 for any A[i] divisible by 2
Next, starting at the first non-zero element after 2,
set to zero all items divisible by that number.
Repeat until you get to the end of the array.

So, 1 is prime?
This can be done without ever performing a divide!

Doesn't need any go-to or test to jump out.
Probably is cleaner to use a while-loop instead of a for-loop.
index = 2;
while ( index < N ) {
/* fill in the rest of the code*/
}

--
Fred L. Kleinschmidt
Boeing Associate Technical Fellow
Technical Architect, Software Reuse Project

[Michael Mair]

Joe Smith schrieb:

It is nothing short of embarrassing to feel the need to ask for help on
this. I can't see how I would make the main control for this. What I want
is a for loop and a test condition. And while I know, from things I
pondered 2 decades ago, that a fella can write code without a goto, I'm
stuck.

/* sieve1.c */

#define whatever 20
#define N whatever
You are not really using whatever.
#include <stdio.h>

int main(void)
{
int i, A[N+1], m, sum;
m and sum are not used.
I'd rather give A a name describing the role of A

/* initialize to 0 */

for (i = 0; i <= N; ++ i) A[i] = 0;
You forgot the algorithm itself.
- set all A[i] to value i
- set the leading non-primes (0 and 1) to 0
- Loop over all i = 0..N:
- if you encounter A[i] != 0, set all A[j],
j = 2*i, 3*i, ..., (N/i)*i, to zero

/* output */
printf("Primes less than N are:\n");
for (i = 2; i <= N; ++ i)
{
if (A[i] == 0)
printf("%d

The other way round: A[i] != 0: output i

If you post to comp.lang.c, please post minimal, compiling
code. In your case, for compiling you at least need
printf("%d\t", i);
}
return 0;
}

Copy & paste your code.
BTW: Not all of the ancient Greeks ended on "os"... ;-)
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

[Joe Smith]

"Michael Mair" <Mi**********@i nvalid.invalid> wrote in message
news:4b******** *****@individua l.net...

Joe Smith schrieb:

It is nothing short of embarrassing to feel the need to ask for help on
this. I can't see how I would make the main control for this. What I
want
is a for loop and a test condition. And while I know, from things I
pondered 2 decades ago, that a fella can write code without a goto, I'm
stuck.

/* sieve1.c */

#define whatever 20
#define N whatever

You are not really using whatever.

#include <stdio.h>

int main(void)
{
int i, A[N+1], m, sum;

m and sum are not used.
I'd rather give A a name describing the role of A

/* initialize to 0 */

for (i = 0; i <= N; ++ i) A[i] = 0;

You forgot the algorithm itself.
- set all A[i] to value i
- set the leading non-primes (0 and 1) to 0
- Loop over all i = 0..N:
- if you encounter A[i] != 0, set all A[j],
j = 2*i, 3*i, ..., (N/i)*i, to zero

/* output */
printf("Primes less than N are:\n");
for (i = 2; i <= N; ++ i)
{
if (A[i] == 0)
printf("%d

The other way round: A[i] != 0: output i

If you post to comp.lang.c, please post minimal, compiling
code. In your case, for compiling you at least need
printf("%d\t", i);
}
return 0;
}

Copy & paste your code.
BTW: Not all of the ancient Greeks ended on "os"... ;-)
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

/* sieve2.c */

#define whatever 20
#define N whatever
#include <stdio.h>

int main(void)
{
int i, A[2*N + 1], index, sum;

/* initialize */

for (i = 0; i <= N; ++ i) A[i] = i;

/* main control */
index = 2;

while (index < N)
{
if (A[index] != 0)
{
sum = index;
while (sum <= N)
{
sum = sum + index;
A[sum] = 0;
}
++ index;
}
}
/* output */
printf("Primes less than N are:\n");
for (i = 2; i <= N; ++ i)
{
if (A[i] != 0) printf("%d ", A[i]);
}
return 0;
}
/* end code */
I know this post is a mess and to read it annoys even myself. My debugger
doesn't want to tell me anything, and while the above compiles, it doesn't
behave. Furthermore, I'm rusty with polite snipping, so I'll beg your
pardon. Joe

[SM Ryan]

"Joe Smith" <gr**********@n etzero.net> wrote:
# It is nothing short of embarrassing to feel the need to ask for help on
# this. I can't see how I would make the main control for this. What I want
# is a for loop and a test condition. And while I know, from things I
# pondered 2 decades ago, that a fella can write code without a goto, I'm
# stuck.
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static void error(char *message) {
fprintf(stderr, "%s\n",message) ;
exit(1);
}

static char *readline(FILE *A) {
char *buffer = 0; int n = 0,m = 0,ch;
for (;;) {
int ch = fgetc(A);
switch (ch) {
case EOF: if (buffer==0) return 0;
case '\n': ch = 0;
}
if (n+1>=m) {
m = 2*(n+1); buffer = realloc(buffer, m);
if (!buffer) error("out of memory");
}
buffer[n++] = ch;
if (!ch) break;
}
return buffer;
}

static void writeline(FILE *B,char *n) {
fputs(n,B); fputc('\n',B);
}

static char *number(int n) {
char b[50],*c;
sprintf(b,"%d", n);
c = malloc(strlen(b )+1);
if (!c) error("out of memory");
strcpy(c,b);
return c;
}

static char *increment(char *n) {
char *digit = n+strlen(n); int carry = 1;
while (carry) {
if (digit==n) {
char *n1 = malloc(1+strlen (n)+1);
if (!n1) error("out of memory");
*n1 = '1'; strcpy(n1+1,n);
carry = 0;
free(n); n = n1;
}else if (*--digit=='9') {
*digit = '0';
carry = 1;
}else {
*digit += 1;
carry = 0;
}
}
return n;
}

static int decrement(char *n) {
char *digit = n+strlen(n); int borrow = 1;
int zero = 1;
while (borrow) {
if (digit==n) {
error("Attempte d to decrement zero.");
}else if (*--digit=='0') {
*digit = '9';
borrow = 1;
}else {
*digit -= 1;
borrow = 0;
}
}
while (*n && zero) zero = *n++=='0';
return zero;
}

static int sieveStep(FILE *A,FILE *B) {
int isprime = 1;
while (1) {
char *prime = readline(A);
char *counter = readline(A);
if (!prime) break;
if (prime && !counter) return -1;
writeline(B,pri me);
if (decrement(coun ter)) {
writeline(B,pri me);
isprime = 0;
}else {
writeline(B,cou nter);
}
free(prime); free(counter);
}
return isprime;
}

static void addPrime(char *current,FILE *PR,FILE *B) {
if (PR) writeline(PR,cu rrent);
writeline(B,cur rent);
writeline(B,cur rent);
}

int main(int N,char **P) {
char *limit = 0; int restart = 0;
FILE *A = 0,*B = 0,*PR = stdout;
char *Apath = "A.sve";
char *Bpath = "B.sve";
char *PRpath = 0;
char *current = 0;
while (++P,--N>0) {
char *p = *P;
if (isdigit(p[0])) {
limit = malloc(strlen(p )+1);
if (!limit) error("out of memory");
strcpy(limit,p) ;
}else if (p[0]=='-' && p[1]=='o' && N>0) {
PRpath = P[1]; P++,N--;
}else {
fprintf(stderr, "unrecognis ed option: %s\n",p);
return 1;
}
}

A = fopen(Apath,"r" );
B = fopen(Bpath,"r" );
if (!A && B) rename((const char*)B,(const char*)A);
if (B) fclose(B);

A = fopen(Apath,"r" );
if (A) {
current = readline(A);
if (current && limit) {
char *t = malloc(strlen(l imit)+1);
if (!t) error("out of memory");
strcpy(t,limit) ;
current = increment(curre nt);
for (restart=1; restart; ) {
char *prime = readline(A);
char *counter = readline(A);
if (!prime) break;
free(prime);
if (prime && !counter) restart = 0;
free(counter);
if (decrement(t)) {
restart = 0;
}else {
break;
}
}
if (restart) {free(limit); limit = t;}
else {free(t);}
}else {
restart = 1;
}
if (!restart) free(current);
fclose(A);
}
if (!PRpath) {
;
}else if (strcmp(PRpath, "none")==0) {
PR = 0;
}else {
PR = fopen(PRpath,re start?"a":"w");
if (!PR) {
perror(PRpath);
return 1;
}
}
if (!restart) {
A = fopen(Apath,"w" );
if (!A) {
perror(Apath);
return 1;
}
current = number(2);
writeline(A,cur rent);
fclose(A);
}
while (1) {
A = fopen(Apath,"r" ); if (!A) {perror(Apath); return 1;}
B = fopen(Bpath,"w" ); if (!B) {perror(Bpath); return 1;}
free(readline(A )); writeline(B,cur rent);
switch (sieveStep(A,B) ) {
case 1:
addPrime(curren t,PR,B);
if (limit && decrement(limit )) return 0;
break;
case -1:
return 1;
}
current = increment(curre nt);
fclose(A);
fclose(B);
if (rename(Bpath,A path)<0) {
fprintf(stderr, "rename %s: ",Bpath); perror(Apath);
return 1;
}
}
}

--
SM Ryan http://www.rawbw.com/~wyrmwif/
If your job was as meaningless as theirs, wouldn't you go crazy too?

[Keith Thompson]

SM Ryan <wy*****@tang o-sierra-oscar-foxtrot-tango.fake.org> writes:
[...]

static void error(char *message) {
fprintf(stderr, "%s\n",message) ;
exit(1);
exit(1) doesn't necessarily indicate an error. Use exit(EXIT_FAILU RE).
} [...] int main(int N,char **P) {
The usual names for the parameters to main are argc and argv. Using N
and P is obfuscation.
fprintf(stderr, "unrecognis ed option: %s\n",p);
return 1;
Again, use EXIT_FAILURE. (There are several other occurrences of
this.)

[...]
if (rename(Bpath,A path)<0) {
fprintf(stderr, "rename %s: ",Bpath); perror(Apath);
return 1;
}

Use more whitespace.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[mensanator]

Joe Smith wrote:

"Michael Mair" <Mi**********@i nvalid.invalid> wrote in message
news:4b******** *****@individua l.net...

Joe Smith schrieb:

It is nothing short of embarrassing to feel the need to ask for help on
this. I can't see how I would make the main control for this. What I
want
is a for loop and a test condition. And while I know, from things I
pondered 2 decades ago, that a fella can write code without a goto, I'm
stuck.

/* sieve1.c */

#define whatever 20
#define N whatever
You are not really using whatever.

#include <stdio.h>

int main(void)
{
int i, A[N+1], m, sum;

m and sum are not used.
I'd rather give A a name describing the role of A

/* initialize to 0 */

for (i = 0; i <= N; ++ i) A[i] = 0;

You forgot the algorithm itself.
- set all A[i] to value i
- set the leading non-primes (0 and 1) to 0
- Loop over all i = 0..N:
- if you encounter A[i] != 0, set all A[j],
j = 2*i, 3*i, ..., (N/i)*i, to zero

/* output */
printf("Primes less than N are:\n");
for (i = 2; i <= N; ++ i)
{
if (A[i] == 0)
printf("%d

The other way round: A[i] != 0: output i

If you post to comp.lang.c, please post minimal, compiling
code. In your case, for compiling you at least need
printf("%d\t", i);
}
return 0;
}

Copy & paste your code.
BTW: Not all of the ancient Greeks ended on "os"... ;-)
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

/* sieve2.c */

#define whatever 20
#define N whatever
#include <stdio.h>

int main(void)
{
int i, A[2*N + 1], index, sum;

/* initialize */

for (i = 0; i <= N; ++ i) A[i] = i;

/* main control */
index = 2;

while (index < N)
{
if (A[index] != 0)
{
sum = index;
while (sum <= N)
{
sum = sum + index;
A[sum] = 0;
}
++ index;
}

/* you need to increment index even when A[index] is 0 */
/* otherwise your while loop never exits */

else
{
++index;
}
}
/* output */
printf("Primes less than N are:\n");
for (i = 2; i <= N; ++ i)
{
if (A[i] != 0) printf("%d ", A[i]);
}
return 0;
}
/* end code */
I know this post is a mess and to read it annoys even myself. My debugger
doesn't want to tell me anything, and while the above compiles, it doesn't
behave. Furthermore, I'm rusty with polite snipping, so I'll beg your
pardon. Joe

[Joe Smith]

<me********@aol .com> wrote in message
news:11******** **************@ v46g2000cwv.goo glegroups.com.. .

Joe Smith wrote:

"Michael Mair" <Mi**********@i nvalid.invalid> wrote in message
news:4b******** *****@individua l.net...

> Joe Smith schrieb:
>> It is nothing short of embarrassing to feel the need to ask for help
>> on
>> this. I can't see how I would make the main control for this. What I
>> want
>> is a for loop and a test condition. And while I know, from things I
>> pondered 2 decades ago, that a fella can write code without a goto,
>> I'm
>> stuck.
>>
>> /* sieve1.c */
>>
>> #define whatever 20
>> #define N whatever
>
> You are not really using whatever.
>
>> #include <stdio.h>
>>
>> int main(void)
>> {
>> int i, A[N+1], m, sum;
>
> m and sum are not used.
> I'd rather give A a name describing the role of A
>
>>
>> /* initialize to 0 */
>>
>> for (i = 0; i <= N; ++ i) A[i] = 0;
>
> You forgot the algorithm itself.
> - set all A[i] to value i
> - set the leading non-primes (0 and 1) to 0
> - Loop over all i = 0..N:
> - if you encounter A[i] != 0, set all A[j],
> j = 2*i, 3*i, ..., (N/i)*i, to zero
>
>>
>> /* output */
>> printf("Primes less than N are:\n");
>> for (i = 2; i <= N; ++ i)
>> {
>> if (A[i] == 0)
>> printf("%d
>
> The other way round: A[i] != 0: output i
>
> If you post to comp.lang.c, please post minimal, compiling
> code. In your case, for compiling you at least need
> printf("%d\t", i);
> }
> return 0;
> }
>
> Copy & paste your code.
>
>
> BTW: Not all of the ancient Greeks ended on "os"... ;-)
>
>
> Cheers
> Michael
> --
> E-Mail: Mine is an /at/ gmx /dot/ de address.

/* sieve2.c */

#define whatever 20
#define N whatever
#include <stdio.h>

int main(void)
{
int i, A[2*N + 1], index, sum;

/* initialize */

for (i = 0; i <= N; ++ i) A[i] = i;

/* main control */
index = 2;

while (index < N)
{
if (A[index] != 0)
{
sum = index;
while (sum <= N)
{
sum = sum + index;
A[sum] = 0;
}
++ index;
}

/* you need to increment index even when A[index] is 0 */
/* otherwise your while loop never exits */

else
{
++index;
}

}
/* output */
printf("Primes less than N are:\n");
for (i = 2; i <= N; ++ i)
{
if (A[i] != 0) printf("%d ", A[i]);
}
return 0;
}
/* end code */
I know this post is a mess and to read it annoys even myself. My
debugger
doesn't want to tell me anything, and while the above compiles, it
doesn't
behave. Furthermore, I'm rusty with polite snipping, so I'll beg your
pardon. Joe

I believe that the line
++ index;
belongs one curly brace down, and
that this would address this shortcoming. Joe

[mensanator]

Joe Smith wrote:

<me********@aol .com> wrote in message
news:11******** **************@ v46g2000cwv.goo glegroups.com.. .

Joe Smith wrote:

"Michael Mair" <Mi**********@i nvalid.invalid> wrote in message
news:4b******** *****@individua l.net...
> Joe Smith schrieb:
>> It is nothing short of embarrassing to feel the need to ask for help
>> on
>> this. I can't see how I would make the main control for this. What I
>> want
>> is a for loop and a test condition. And while I know, from things I
>> pondered 2 decades ago, that a fella can write code without a goto,
>> I'm
>> stuck.
>>
>> /* sieve1.c */
>>
>> #define whatever 20
>> #define N whatever
>
> You are not really using whatever.
>
>> #include <stdio.h>
>>
>> int main(void)
>> {
>> int i, A[N+1], m, sum;
>
> m and sum are not used.
> I'd rather give A a name describing the role of A
>
>>
>> /* initialize to 0 */
>>
>> for (i = 0; i <= N; ++ i) A[i] = 0;
>
> You forgot the algorithm itself.
> - set all A[i] to value i
> - set the leading non-primes (0 and 1) to 0
> - Loop over all i = 0..N:
> - if you encounter A[i] != 0, set all A[j],
> j = 2*i, 3*i, ..., (N/i)*i, to zero
>
>>
>> /* output */
>> printf("Primes less than N are:\n");
>> for (i = 2; i <= N; ++ i)
>> {
>> if (A[i] == 0)
>> printf("%d
>
> The other way round: A[i] != 0: output i
>
> If you post to comp.lang.c, please post minimal, compiling
> code. In your case, for compiling you at least need
> printf("%d\t", i);
> }
> return 0;
> }
>
> Copy & paste your code.
>
>
> BTW: Not all of the ancient Greeks ended on "os"... ;-)
>
>
> Cheers
> Michael
> --
> E-Mail: Mine is an /at/ gmx /dot/ de address.

/* sieve2.c */

#define whatever 20
#define N whatever
#include <stdio.h>

int main(void)
{
int i, A[2*N + 1], index, sum;

/* initialize */

for (i = 0; i <= N; ++ i) A[i] = i;

/* main control */
index = 2;

while (index < N)
{
if (A[index] != 0)
{
sum = index;
while (sum <= N)
{
sum = sum + index;
A[sum] = 0;
}
++ index;
}

/* you need to increment index even when A[index] is 0 */
/* otherwise your while loop never exits */

else
{
++index;
}

}
/* output */
printf("Primes less than N are:\n");
for (i = 2; i <= N; ++ i)
{
if (A[i] != 0) printf("%d ", A[i]);
}
return 0;
}
/* end code */
I know this post is a mess and to read it annoys even myself. My
debugger
doesn't want to tell me anything, and while the above compiles, it
doesn't
behave. Furthermore, I'm rusty with polite snipping, so I'll beg your
pardon. Joe

I believe that the line
++ index;
belongs one curly brace down, and
that this would address this shortcoming. Joe

There's a simple way to find out.