469,620 Members | 1,857 Online

# algorithm by eratosthenos

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

Apr 27 '06 #1
22 1971

"Joe Smith" <gr**********@netzero.net> wrote in message
news:44***********************@news.usenetmonster. 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
Apr 27 '06 #2

Fred Kleinschmidt wrote:
"Joe Smith" <gr**********@netzero.net> wrote in message
news:44***********************@news.usenetmonster. 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

Apr 27 '06 #3
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.
Apr 27 '06 #4

"Michael Mair" <Mi**********@invalid.invalid> wrote in message
news:4b*************@individual.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
Apr 27 '06 #5
"Joe Smith" <gr**********@netzero.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("Attempted 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,prime);
if (decrement(counter)) {
writeline(B,prime);
isprime = 0;
}else {
writeline(B,counter);
}
free(prime); free(counter);
}
return isprime;
}

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

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,"unrecognised 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) {
if (current && limit) {
char *t = malloc(strlen(limit)+1);
if (!t) error("out of memory");
strcpy(t,limit);
current = increment(current);
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,restart?"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,current);
fclose(A);
}
while (1) {
A = fopen(Apath,"r"); if (!A) {perror(Apath); return 1;}
B = fopen(Bpath,"w"); if (!B) {perror(Bpath); return 1;}
switch (sieveStep(A,B)) {
case 1:
if (limit && decrement(limit)) return 0;
break;
case -1:
return 1;
}
current = increment(current);
fclose(A);
fclose(B);
if (rename(Bpath,Apath)<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?
Apr 27 '06 #6
SM Ryan <wy*****@tango-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_FAILURE).
} [...] 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,"unrecognised option: %s\n",p);
return 1;
Again, use EXIT_FAILURE. (There are several other occurrences of
this.)

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

Use more whitespace.

--
Keith Thompson (The_Other_Keith) 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.
Apr 27 '06 #7

Joe Smith wrote:
"Michael Mair" <Mi**********@invalid.invalid> wrote in message
news:4b*************@individual.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

Apr 28 '06 #8

<me********@aol.com> wrote in message

Joe Smith wrote:
"Michael Mair" <Mi**********@invalid.invalid> wrote in message
news:4b*************@individual.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
Apr 28 '06 #9

Joe Smith wrote:
<me********@aol.com> wrote in message

Joe Smith wrote:
"Michael Mair" <Mi**********@invalid.invalid> wrote in message
news:4b*************@individual.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.

Apr 28 '06 #10
Keith Thompson wrote:
SM Ryan <wy*****@tango-sierra-oscar-foxtrot-tango.fake.org> writes:
int main(int N,char **P) {

The usual names for the parameters to main are argc and argv. Using N
and P is obfuscation.

I'm curious, how do you feel about int main(int ac, char **av)? Almost
all of my code begins with:
int main(int ac, char **av)
{
struct args args;
parse_args(&args, ac, av);
...
}
so the names are rarely visible (which makes me think I shouldn't be so
lazy and could easily type "rg" an extra 4 times, although one could
argue that parse_args must use the names "argv" and "argc" as well.)

I'm curious to see opinions on that style.

Also, is there any difference between the declarations:
char *const*av and
char *av[]?
I'm still unclear which ought to be used in place of char **.

Apr 28 '06 #11
"Bill Pursell" <bi**********@gmail.com> wrote:
# Keith Thompson wrote:
# > SM Ryan <wy*****@tango-sierra-oscar-foxtrot-tango.fake.org> writes:
# > > int main(int N,char **P) {
# >
# > The usual names for the parameters to main are argc and argv. Using N
# > and P is obfuscation.
#
# I'm curious, how do you feel about int main(int ac, char **av)? Almost

Poor Kiethey is just jealous. It's version of the sieve that can
handle primes of millions of digit--depends only on holding two numbers
in memory and the rest on disc.

--
SM Ryan http://www.rawbw.com/~wyrmwif/
So....that would make Bethany part black?
Apr 28 '06 #12
"Bill Pursell" <bi**********@gmail.com> writes:
Keith Thompson wrote:
SM Ryan <wy*****@tango-sierra-oscar-foxtrot-tango.fake.org> writes:
> int main(int N,char **P) {
The usual names for the parameters to main are argc and argv. Using N
and P is obfuscation.

I'm curious, how do you feel about int main(int ac, char **av)?

About the same way.
Almost all of my code begins with:
int main(int ac, char **av)
{
struct args args;
parse_args(&args, ac, av);
...
}
so the names are rarely visible (which makes me think I shouldn't be so
lazy and could easily type "rg" an extra 4 times, although one could
argue that parse_args must use the names "argv" and "argc" as well.)

I'm curious to see opinions on that style.
You can legally use any names you like, but I honestly can't think of
any good reason not to use argc and argv. Can you think of *any*
reason why ac and av is better than argc and argv?
Also, is there any difference between the declarations:
char *const*av and
char *av[]?
I'm still unclear which ought to be used in place of char **.

What's wrong with char **? And why do you want to add a "const"?

In an argument declaration, "char *argv[]" and "char **argv" are
exactly equivalent.

--
Keith Thompson (The_Other_Keith) 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.
Apr 28 '06 #13

<me********@aol.com> wrote in message

Fred Kleinschmidt wrote:
"Joe Smith" <gr**********@netzero.net> wrote in message
news:44***********************@news.usenetmonster. 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?

Only in regards to: So, 1 is prime?

No. Zero (0) and one (1) are not prime. One is not prime by collusion of
mathematicians. Certain mathematical proofs suggest one is prime, however,
when one is used as a prime in other more advanced proofs, it causes extra
complexity in the proof.
Rod Pemberton
Apr 28 '06 #14

"Joe Smith" <gr**********@netzero.net> wrote in message
news:44***********************@news.usenetmonster. 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

I'll post some code, but let's review a few things about primes. zero and
one aren't prime. two is the only even that is prime. five is the only odd
ending with a decimal digit of five that is prime. In other words:

0: not prime
1: not prime
2: prime
5: prime
evens other than 2: not prime
odds ending in 1,3,7: must be tested for primality.

The following code will generate primes greater than 3. A test for values
ending in 5 slows it down the inner loop too much. As the code shows, you
only need to test values as factors of a number upto the square root of that
number. This is done without using a sqrt() function.
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
unsigned long long counter,i=0,j,primes=0;
int prime_found;

counter = 3; /* init to prime 3 */

for (;;)
{
prime_found=0;
for(i=3,j=4;j<=counter;i+=2,j+=i)
/* i is the prime number to test as a factor of counter */
/* j is the square of i which is used to indicate that */
/* we have reached or exceeded the square root of counter */
/* the square root of counter is the largest possible factor */
/* for which there can be no larger value prime factor of counter
*/
/* we have moved from the outlying large and small primes and */
/* reached the middlemost primes of counter */
{
if((counter % i)==0) /* test prime as factor */
{
prime_found =1; /* not a prime... */
break;
}
}
if (prime_found==0) /* prime number */
{
primes++;
printf("%llu:%llu:%llx\n",primes,counter,counter);
}
counter+=2;
}

exit(EXIT_SUCCESS);
}
Rod Pemberton
Apr 28 '06 #15
Joe Smith schrieb:
"Michael Mair" <Mi**********@invalid.invalid> wrote in message
news:4b*************@individual.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.
<snip>
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
<snip>
/* sieve2.c */

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

int main(void)
{
int i, A[2*N + 1], index, sum;
Where does the factor 2 come in?

/* 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

No problem. Please try to indent your code (preferably with spaces);
this makes it much easier to read it.

The following implements the suggested algorithm and works at first
glance.
Note that this code does not try to be intelligent: It stupidly
implements the algorithm. This is the best for your first shot
at something: Keep it plain and simple.
Afterwards you can think about reducing the programme's memory
consumption and loop numbers -- and compare the output to the
obviously working version...

/* sieve2.c */
#include <stdio.h>

#define MAX_TESTED_NUMBER 20
int main (void)
{
int i, A[MAX_TESTED_NUMBER + 1];

/* initialize */
for (i = 0; i <= MAX_TESTED_NUMBER; ++i)
A[i] = i;
A[0] = A[1] = 0; /* Eliminate non-primes */

/* main control */

for (i = 0; i <= MAX_TESTED_NUMBER; ++i)
{
if (A[i] != 0)
{
int j = 2*i;
while (j <= MAX_TESTED_NUMBER)
{
A[j] = 0;
j += i;
}
}
}

/* output */
printf("Primes between 0 and %d are:\n", MAX_TESTED_NUMBER);
for (i = 0; i <= MAX_TESTED_NUMBER; ++i)
{
if (A[i] != 0)
printf("%d ", A[i]);
}

return 0;
}
/* end code */

Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
Apr 28 '06 #16
Joe Smith schrieb:
"Michael Mair" <Mi**********@invalid.invalid> wrote in message
news:4b*************@individual.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.
<snip>
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
<snip>
/* sieve2.c */

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

int main(void)
{
int i, A[2*N + 1], index, sum;
Where does the factor 2 come in?

/* 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

No problem. Please try to indent your code (preferably with spaces);
this makes it much easier to read it.

The following implements the suggested algorithm and works at first
glance.
Note that this code does not try to be intelligent: It stupidly
implements the algorithm. This is the best for your first shot
at something: Keep it plain and simple.
Afterwards you can think about reducing the programme's memory
consumption and loop numbers -- and compare the output to the
obviously working version...

/* sieve2.c */
#include <stdio.h>

#define MAX_TESTED_NUMBER 20
int main (void)
{
int i, A[MAX_TESTED_NUMBER + 1];

/* initialize */
for (i = 0; i <= MAX_TESTED_NUMBER; ++i)
A[i] = i;
A[0] = A[1] = 0; /* Eliminate non-primes */

/* main control */

for (i = 0; i <= MAX_TESTED_NUMBER; ++i)
{
if (A[i] != 0)
{
int j = 2*i;
while (j <= MAX_TESTED_NUMBER)
{
A[j] = 0;
j += i;
}
}
}

/* output */
printf("Primes between 0 and %d are:\n", MAX_TESTED_NUMBER);
for (i = 0; i <= MAX_TESTED_NUMBER; ++i)
{
if (A[i] != 0)
printf("%d ", A[i]);
}

return 0;
}
/* end code */

Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
Apr 28 '06 #17
Keith Thompson wrote:
"Bill Pursell" <bi**********@gmail.com> writes:
Keith Thompson wrote:
SM Ryan <wy*****@tango-sierra-oscar-foxtrot-tango.fake.org> writes:
> int main(int N,char **P) {

The usual names for the parameters to main are argc and argv. Using N
and P is obfuscation.
I'm curious, how do you feel about int main(int ac, char **av)?

About the same way.

<snip> You can legally use any names you like, but I honestly can't think of
any good reason not to use argc and argv. Can you think of *any*
reason why ac and av is better than argc and argv?

It's 2 characters less. I won't argue that that's a *good* reason, but
it is the only reason I do it, and now my fingers are accustomed
to it.
Also, is there any difference between the declarations:
char *const*av and
char *av[]?
I'm still unclear which ought to be used in place of char **.

What's wrong with char **? And why do you want to add a "const"?

I like char **, but I've seen some people argue that char *av[] is more
correct. I'm not sure if they were arguing about style or substance.
The thing that prompted me to add the const was a minor mishap with
getopt. I had done:
void parse_args (struct args_s *args, int argc, const char **argv)
{
...
getopt(argc, argv, optstring)
....
and was rejected because the 2nd parameter to getopt is prototyped as
char *const argv[]. So I had to change the declaration of parse_args
to match, and that got me thinking that the argument list for main
might as well match.

Apr 28 '06 #18

<me********@aol.com> wrote in message

Joe Smith wrote:
<me********@aol.com> wrote in message
>
> Joe Smith wrote:
>> "Michael Mair" <Mi**********@invalid.invalid> wrote in message
>> news:4b*************@individual.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"... ;-)
Any talk of an os around here will meet with certain consternation:-)
>> >
>> >
>> > 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.

/* sieve3.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 think that does it. One thing that really threw me about this was that I
was trying to imitate the way one might do it on the back of a napkin while
tutoring. Now I'm wondering if there's a way of calculating this that heats
up the atmosphere less. Joe
Apr 28 '06 #19
Bill Pursell wrote:
.... snip ... ...
getopt(argc, argv, optstring)
...
and was rejected because the 2nd parameter to getopt is prototyped
as char *const argv[]. So I had to change the declaration of
parse_args to match, and that got me thinking that the argument
list for main might as well match.

Which is just plain wrong. You can modify **argv. You can't
modify *argv. You can't lengthen the string at *argv either.

--
"The power of the Executive to cast a man into prison without
formulating any charge known to the law, and particularly to
deny him the judgement of his peers, is in the highest degree
odious and is the foundation of all totalitarian government
whether Nazi or Communist." -- W. Churchill, Nov 21, 1943
Apr 29 '06 #20
CBFalconer wrote:
Bill Pursell wrote:

... snip ...
...
getopt(argc, argv, optstring)
...
and was rejected because the 2nd parameter to getopt is prototyped
as char *const argv[]. So I had to change the declaration of
parse_args to match, and that got me thinking that the argument
list for main might as well match.

Which is just plain wrong. You can modify **argv. You can't
modify *argv. You can't lengthen the string at *argv either.

What is wrong? The prototype for getopt, or prototyping main as taking
(char *const*argv)? It seems that you 2nd and 3rd sentence, are
semantically equivalent to prototyping main as (int argc, char
*const*argv), so I'm not sure what you're saying. Obviously, if we
protoype main as taking a char **, then we CAN change *argv (and I
think you are claiming that we shouldn't):

#include <stdio.h>

int main (int argc, char **argv)

{
printf("argv[0] = %s\n", argv[0]);
*argv += 1;
printf("argv[0] = %s\n", argv[0]);

return 0;
}

Apr 29 '06 #21
Bill Pursell schrieb:
CBFalconer wrote:
Bill Pursell wrote:

... snip ...
...
getopt(argc, argv, optstring)
...
and was rejected because the 2nd parameter to getopt is prototyped
as char *const argv[]. So I had to change the declaration of
parse_args to match, and that got me thinking that the argument
list for main might as well match.

Which is just plain wrong. You can modify **argv. You can't
modify *argv. You can't lengthen the string at *argv either.

What is wrong? The prototype for getopt, or prototyping main as taking
(char *const*argv)? It seems that you 2nd and 3rd sentence, are
semantically equivalent to prototyping main as (int argc, char
*const*argv), so I'm not sure what you're saying. Obviously, if we
protoype main as taking a char **, then we CAN change *argv (and I
think you are claiming that we shouldn't):

#include <stdio.h>

int main (int argc, char **argv)

{
printf("argv[0] = %s\n", argv[0]);
*argv += 1;
printf("argv[0] = %s\n", argv[0]);

return 0;
}

From C99 5.2.2.1:
"The parameters argc and argv and the strings pointed to by the argv
array shall be modifiable by the program, and retain their last-stored
values between program startup and program termination."

This especially does not mention *argv.
I.e. you are allowed to do argv++ and argv[0][0] = 42 but I'd not rely
on argv[0]++ to work. I guess that we do not have "char * const *"
type for the second type only for historical reasons.
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
Apr 29 '06 #22
>>> >> 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
[snips everyone but himself]
/* sieve3.c */

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

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

I endeavor to take keystrokes and have the prog create the memory at
runtime.
My first problem is that I'm unaware of how to get an integer without having
to build them from chars and then first principles. I can recall no such
K&R
exercise. Let's assume, however that we have an N from the keyboard that
happens to equal 20.

p = malloc( (N + 1) * sizeof(int));
is what I want to write.

Well, it doesn't look like this sieve is going to work tonight nearly as
well
as that 4 by 6 region behind the Redwing's goalie did. One thing that
would help me to know what this code says is having a debugger that is aware
of any executable. Any help is appreciated. Joe
May 2 '06 #23

### This discussion thread is closed

Replies have been disabled for this discussion.