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
22  2154 
"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
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
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.
"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
"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) {
current = readline(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;}
free(readline(A)); writeline(B,current);
switch (sieveStep(A,B)) {
case 1:
addPrime(current,PR,B);
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?
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.
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
<me********@aol.com> wrote in message
news:11**********************@v46g2000cwv.googlegr oups.com...
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
Joe Smith wrote: <me********@aol.com> wrote in message
news:11**********************@v46g2000cwv.googlegr oups.com...
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.
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 **.
"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?
"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.
<me********@aol.com> wrote in message
news:11**********************@i40g2000cwc.googlegr oups.com...
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
"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
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.
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.
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.
<me********@aol.com> wrote in message
news:11**********************@j33g2000cwa.googlegr oups.com...
Joe Smith wrote: <me********@aol.com> wrote in message
news:11**********************@v46g2000cwv.googlegr oups.com... >
> 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
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
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;
}
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.
>>> >> 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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Jack Smith |
last post by:
Hello, any help appreciated with following problem. I figured out the
algorithm (I think), just having trouble proving it is optimal.
Suppose we are given n tasks each of which takes 1 unit...
|
by: cody |
last post by:
I have to write an algorithm with must ensure that objects are put in
buckets (which are always 4 in size).
The objects have two properties: A and B. It is not allowed that in a bucket
are objects...
|
by: bpontius |
last post by:
The GES Algorithm
A Surprisingly Simple Algorithm for Parallel Pattern Matching
"Partially because the best algorithms presented in the literature
are difficult to understand and to implement,...
|
by: Cmorriskuerten |
last post by:
HI,
is this is this solution to test if a number is a prime number or not:
/*
* Is n a prime number?
* Return TRUE (1): n is a prime number
* Return FALSE (0): n is a *not* a prime number...
|
by: Bonj |
last post by:
I was in need of an encryption algorithm to the following requirements:
1) Must be capable of encrypting strings to a byte array, and decyrpting
back again to the same string
2) Must have the same...
|
by: FBM |
last post by:
Hi,
I am working on a program that simulates one of the elements of ATM.
The simulation stores events which occurs every some milliseconds for a
certain amount of time. Every time that an event...
|
by: Julio C. Hernandez Castro |
last post by:
Dear all,
We have just developped a new block cipher called Raiden, following a
Feistel Network structure by means of genetic programming. Our
intention now consists on getting as much feedback...
|
by: aruna |
last post by:
hey guys i earlier had very valuable responses from you all for base64
encoding algorithm.so thank for that. so now i need your assistance to
do a float encoding algorithm. you may wonder why i'm...
|
by: almurph |
last post by:
Hi everyone,
Concerning the Needleman-Wunsch algorithm (cf.
http://en.wikipedia.org/wiki/Needleman-Wunsch_algorithm) I have
noticed a possible loop.
Inside the algorithm there is an...
|
by: taylorcarr |
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
| |
