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

[Bill Pursell]

Keith Thompson wrote:

SM Ryan <wy*****@tang o-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(&arg s, 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 **.

[SM Ryan]

"Bill Pursell" <bi**********@g mail.com> wrote:
# Keith Thompson wrote:
# > SM Ryan <wy*****@tang o-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?

[Keith Thompson]

"Bill Pursell" <bi**********@g mail.com> writes:

Keith Thompson wrote:

SM Ryan <wy*****@tang o-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(&arg s, 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_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.

[Rod Pemberton]

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

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?

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

[Rod Pemberton]

"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

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,p rimes=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:%l lu:%llx\n",prim es,counter,coun ter);
}
counter+=2;
}

exit(EXIT_SUCCE SS);
}
Rod Pemberton

[Michael Mair]

Joe Smith schrieb:

"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.

<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_NUMB ER 20
int main (void)
{
int i, A[MAX_TESTED_NUMB ER + 1];

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

/* main control */

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

/* output */
printf("Primes between 0 and %d are:\n", MAX_TESTED_NUMB ER);
for (i = 0; i <= MAX_TESTED_NUMB ER; ++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.

[Michael Mair]

Joe Smith schrieb:

"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.

<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_NUMB ER 20
int main (void)
{
int i, A[MAX_TESTED_NUMB ER + 1];

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

/* main control */

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

/* output */
printf("Primes between 0 and %d are:\n", MAX_TESTED_NUMB ER);
for (i = 0; i <= MAX_TESTED_NUMB ER; ++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.

[Bill Pursell]

Keith Thompson wrote:

"Bill Pursell" <bi**********@g mail.com> writes:

Keith Thompson wrote:

SM Ryan <wy*****@tang o-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.

[Joe Smith]

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

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"... ;-)
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

[CBFalconer]

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