simple algorithm for finding primes

[someone else]

hi all

I'm a newbie to this group. my apologies if I break any rules.

I've wrote a simple program to find the first 1,000,000 primes, and to find
all primes within any range (up to 200 * 10^12)

it's pretty efficient, it took 15 minutes to compute the first 1,000,000
primes.

I would like to here your opinion about it

p.s. I'm not a mathematician, in fact, my math level is primary school
(hardly).

please Cc all replies to (e-mail address removed)

replace the aesqq with (hrneo) before the @,

thanks

michael



//compiler: ms visual c++ 7.0

#include <stdio.h>

#include <conio.h>

#include <math.h>



int main()

{

long nth,pause;



//************collect info from user**************

printf("\t***WELCOME***\nthis program displays all prime numbers up to about
2 billion\nsince the output proccess taks a lot of resources,if you wish to
display large numbers, it is recommended that you set the Nth prime to be
larger then 100");

printf("\n\nplease enter the Nth prine to be displayed, if you select 10,
the 10th, 20th, 30th... primes will be displayed.\n\nplease select a number
between 1 and 10,000, or 0 to exit\n");

fflush(stdin);

scanf("%d",&nth);

if (!nth) return 0;

printf("please enter after how meny numbers to pause. plese select a number
between 2 and 10,000\n");

fflush(stdin);

scanf("%d",&pause);

//************end collect info from user**************



//create and arry to store the first 5000 primes:

long *prime = new long[1000000];long counter=3;bool flag =1;



prime[0]=1;prime[1]=2;prime[2]=3; //set the first three primes

printf("\n\n\t\t---finished\n\n"); getch();



// i is the number that will be checked if it's a prime

//loop with i = 5 initially, add 2 to i evey cycle,terminate if the counter
is greater then 10000000



for (long i=5;counter<1000000;i+=2,flag=1)

{

//check all primes that satisfy sqrt(i) >= prime

for (long j=2;prime[j]<long(sqrt(double(i))+1);j++)

{

if (i%prime[j]==0)//i is not a prime, go back to the first loop

{

flag=0;

break;

}

}


if (flag)

// now we know that i is a prime (since it's not divisible by any prime that
( root(i) >= prime )

{

prime[counter]=i;

counter++;

if(counter%nth==0) printf("\t%ld",i);

if (counter%(nth*pause)==0) getch();

flag=0;

}

else

continue;

}

printf("\n\n***************************finished******************\n\npress
any key to exit");

getch();

return 0;

}

/**************************

//code to store the first 1000000 primes to a binary file:

//place the code at the END of the file

FILE *fp=fopen("15000pri.bin","r+b");

if (!fp) printf("unable to open file");

fwrite(prime,sizeof(prime)*1000000,1,fp);

if (fclose(fp))

printf("\n\nfile not closed\n\n");

else

printf("\n\nfile successfully closed\n\n");

getch();

//code to get the first 1000000 primes from the binary file:

//place the code right after the declaration of *prime

FILE *fp=fopen("15000pri.bin","r+b");

if (!fp) printf("unable to open file");

fread(prime,sizeof(prime)*1000000,1,fp);

if (fclose(fp))

printf("\n\nfile not closed\n\n");

else

printf("\n\nfile successfully closed\n\n");

getch();



//code to check the chances of a number being a prime when number%pause==0

// pause is a variable entered by the user



double chance = 1.0;

for (long k=1;k<1000000;k++)

{

if (k%(pause/1000)==0) printf("%ld ",prime[k]);

chance -= double(1.0/double(prime[k])*chance);

if (k%pause==0) {printf("\t%f\t%ld",chance,k); getch(); }

}

//code to check primes within a range (maximum 1,000,000,000,000)

// you must have the first 1,000,000 primes loaded from a file or calculated
into the array (prime[1000000])

__int64 lower,upper;

printf("\n\nplease enter the lower range.\n\nplease select a number between
5 and 10^12 (1, and 12 zeroes) , or 0 to exit\n");

fflush(stdin);

scanf("%I64",&lower);

if (!nth) return 0;

printf("please enter the lower range.\n\nplease select a number between 5
and 10^12 (1, and 12 zeroes)");

fflush(stdin);

scanf("%I64",&upper);

if (upper<5 || upper>pow(10.0,12.0) || lower<5 || lower>pow(10.0,12.0))

{ printf("invalid range...exiting"); getch(); return 0; }



for (__int64 l=lower;l<=upper;l+=2,flag=1)

{

//check all primes that satisfy sqrt(i) >= prime

for (long m=2;prime[m]<long(sqrt(double(l))+1);m++)

{

if (l%prime[m]==0)//i is not a prime, go back to the first loop

{

flag=0;

break;

}

}


if (flag)

// now we know that i is a prime (since it's not divisible by any prime that
( root(i) >= prime )

{

printf("\t%I64",l);

flag=0;

}

else

continue;

}

//****************************/

 

[Jack Klein]

hi all

Hi yourself.

I'm a newbie to this group. my apologies if I break any rules.

One very important one, as a matter of fact.

I've wrote a simple program to find the first 1,000,000 primes, and to find
all primes within any range (up to 200 * 10^12)

it's pretty efficient, it took 15 minutes to compute the first 1,000,000
primes.

I would like to here your opinion about it

p.s. I'm not a mathematician, in fact, my math level is primary school
(hardly).

please Cc all replies to (e-mail address removed)

replace the aesqq with (hrneo) before the @,

thanks

michael

//compiler: ms visual c++ 7.0

#include <stdio.h>

#include <conio.h>

Non-standard header.

#include <math.h>

int main()
{

long nth,pause;

//************collect info from user**************

printf("\t***WELCOME***\nthis program displays all prime numbers up to about
2 billion\nsince the output proccess taks a lot of resources,if you wish to
display large numbers, it is recommended that you set the Nth prime to be
larger then 100");

printf("\n\nplease enter the Nth prine to be displayed, if you select 10,
the 10th, 20th, 30th... primes will be displayed.\n\nplease select a number
between 1 and 10,000, or 0 to exit\n");

fflush(stdin);

Oh, there you've gone and invoked undefined behavior. The fflush()
function is undefined on input streams.

scanf("%d",&nth);

Undefined behavior if the value typed in by the user is outside the
range of a signed int.

if (!nth) return 0;

printf("please enter after how meny numbers to pause. plese select a number
between 2 and 10,000\n");

fflush(stdin);

scanf("%d",&pause);

//************end collect info from user**************



//create and arry to store the first 5000 primes:

long *prime = new long[1000000];long counter=3;bool flag =1;

Here's the biggest rule that you broke:

***THIS IS NOT C CODE AT ALL***

There is no such thing as "new" in C, nor is there a type "bool"
unless you have a compiler that supports C99's <stdbool.h> header and
have included that header. That leaves out every single Microsoft
compiler released to data.

[snip]

printf("\n\n\t\t---finished\n\n"); getch();

There is no function named getch() in either the C or C++ language.

Overall, your code is littered with non-standard Microsoft specific
extensions that are not part of either standard C or C++. You should
not be posting to comp.lang.c or comp.lang.c++ until you at least know
the difference between C and C++. A better place for you might be the
group until you know more.

You should also get a good C programming book if you want to use C,
like one of these two excellent choices:

The C Programming Language, Second Edition
Brian W. Kernighan & Dennis M. Ritchie
Prentice Hall 1988
Hardcover ISBN 0131103709
Softcover ISBN 0131103628

C Programming: A Modern Approach
K. N. King
W. W. Norton & Company 1996
Softcover ISBN 0393969452

Finally, you are reinventing a well-rounded wheel. Do a Google search
on the phrase "Sieve of Eratosthenes" to find an algorithm that is
several thousand years old.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++ ftp://snurse-l.org/pub/acllc-c++/faq

 

[someone else]

Sieve of Eratosthenes:

Make a list of all the integers less than or equal to n (and greater than
one).
Strike out the multiples of all primes less than or equal to the square root
of n.
Then the numbers that are left are the primes.

Hi yourself.


One very important one, as a matter of fact.


Non-standard header.

duh!

Oh, there you've gone and invoked undefined behavior. The fflush()
function is undefined on input streams.


Undefined behavior if the value typed in by the user is outside the
range of a signed int.

sorry, my mistake, i meant the first 1,000,000 primes

long *prime = new long[1000000];long counter=3;bool flag =1;

Here's the biggest rule that you broke:

***THIS IS NOT C CODE AT ALL***

There is no such thing as "new" in C, nor is there a type "bool"
unless you have a compiler that supports C99's <stdbool.h> header and
have included that header. That leaves out every single Microsoft
compiler released to data.

true, i could have used:
long *prime = malloc(sizeof(long)*1000000)
but i tried to keep the code more readable by avoiding the use of pointers,
and "bool" could as well have been int

[snip]

printf("\n\n\t\t---finished\n\n"); getch();

There is no function named getch() in either the C or C++ language.

getch() is an istruction to pause the DOS console until a key is pressed so
it has to be platform specific and non standard.

Overall, your code is littered with non-standard Microsoft specific
extensions that are not part of either standard C or C++. You should
not be posting to comp.lang.c or comp.lang.c++ until you at least know
the difference between C and C++. A better place for you might be the
group until you know more.

You should also get a good C programming book if you want to use C,
like one of these two excellent choices:

The C Programming Language, Second Edition
Brian W. Kernighan & Dennis M. Ritchie
Prentice Hall 1988
Hardcover ISBN 0131103709
Softcover ISBN 0131103628

C Programming: A Modern Approach
K. N. King
W. W. Norton & Company 1996
Softcover ISBN 0393969452

Finally, you are reinventing a well-rounded wheel. Do a Google search
on the phrase "Sieve of Eratosthenes" to find an algorithm that is
several thousand years old.

as i quoted at the beggining, Sieve of Eratosthenes is based on creating an
array of all numbers, while i only created an array of primes, i'm aware
that there are more comlex ways of checking for primes but they require a
university degree in math, and most of them only say that the number is
"allmost sertainly a prime" while my way is absolutely certain, and can be
undestood by non mathematician's.
and finally, since there's no 64 bit integers in standard c, i used
microsoft's implementation, i could have as well used other libraries for 64
bit integers.

all i can say is that if things as nimor as getch() disturb you, i shouldn't
post here anymore, and news:comp.alt.lang.learn.c-c++ is a non active groupmichael

 

[CBFalconer]

.... snip ..

all i can say is that if things as nimor as getch() disturb you,
i shouldn't post here anymore, and is a non active group

From the rear: No, one of news:comp.lang.learn.c-c++ and

is not non-active. Maybe you
shouldn't. The pronoun 'I' should be capitalized. getch() does
not exist in standard C. The word nimor is unknown to me. The
pronoun 'I' should be capitalized. Sentences should usually begin
with a capital letter.

Should nimor be intended to mean normal, the point is that getch
is not a normal thing in C programs, except within the relatively
small subset using certain compilers under certain operating
systems, and thus there is no reason to make any assumptions
whatsoever about what getch does.

 

[Grumble]

Overall, your code is littered with non-standard Microsoft specific
extensions that are not part of either standard C or C++. You should
not be posting to comp.lang.c or comp.lang.c++ until you at least know
the difference between C and C++. A better place for you might be the
group news:comp.alt.lang.learn.c-c++ until you know more.

I think you meant alt.comp.lang.learn.c-c++ (there is not comp.alt
hierarchy).

 

[osmium]

as i quoted at the beggining, Sieve of Eratosthenes is based on creating an
array of all numbers, while i only created an array of primes, i'm aware
that there are more comlex ways of checking for primes but they require a
university degree in math, and most of them only say that the number is
"allmost sertainly a prime" while my way is absolutely certain, and can be
undestood by non mathematician's.
and finally, since there's no 64 bit integers in standard c, i used
microsoft's implementation, i could have as well used other libraries for 64
bit integers.

The place to tell us that (sieve) was in a comment in the program, not in a
rebuttal to a Usenet thread.

You will be treated more seriously if you use standard, formal English. The
headers on your post indicate you have a spell checker available. Also, get
rid of all that white space.

You might be happier in a forum or chat room or bulletin board or something.
Richard Heathfield mentioned a chat room, IIRC a week or so ago. You might
try to find that using google advanced groups. The other newsgroup
suggested is also anal retentive WRT things such as getch(). I would expect
a more relaxed attitude in some of these other access methods, though I have
never tried them.

 

[August Derleth]

Sieve of Eratosthenes:

Make a list of all the integers less than or equal to n (and greater than
one).
Strike out the multiples of all primes less than or equal to the square root
of n.
Then the numbers that are left are the primes.

Yes. We know this. We've probably programmed it in more languages than
you even know of.

duh!

Please try not to be rude. If you must be rude, try not to be stupid.

Since it's non-standard, it's off-topic here. Try another newsgroup.

true, i could have used:
long *prime = malloc(sizeof(long)*1000000)
but i tried to keep the code more readable by avoiding the use of pointers,
and "bool" could as well have been int

And in doing so, you wrote code that isn't C and has no place here.
Try again later, with some brains and common courtesy.

[snip]

printf("\n\n\t\t---finished\n\n"); getch();

There is no function named getch() in either the C or C++ language.

getch() is an istruction to pause the DOS console until a key is pressed so
it has to be platform specific and non standard.

You understand that much and yet are still so clueless.

comp.lang.c is for discussing Standard C. Any reading of the FAQ would
tell you that. You did read the FAQ, didn't you?

If not, goodbye.

all i can say is that if things as nimor as getch() disturb you, i shouldn't
post here anymore, and news:comp.alt.lang.learn.c-c++ is a non active group

Finally, you get it. Goodbye.

 

[Randy Howard]

The word nimor is unknown to me.

My guess would be "minor".

 

[someone else]

hi all

I'm a newbie to this group. my apologies if I break any rules.

I've wrote a simple program to find the first 1,000,000 primes, and to find
all primes within any range (up to 200 * 10^12)

it's pretty efficient, it took 15 minutes to compute the first 1,000,000
primes.

I would like to here your opinion about it
I sincerely apologise for not following the rules last time.
and I would really appreciate RELEVANT responses,
p.s. I'm not a mathematician, in fact, my math level is primary school
(hardly).

thanks

Michael



//compiler: ms visual c++ 7.0
#include <stdio.h>
#include <math.h>

int main()
{
long nth,pause;

//************collect info from user**************

printf("\t***WELCOME***\nthis program displays all prime numbers up to about
2 billion\nsince the output process takes a lot of resources,if you wish to
display large numbers, it is recommended that you set the Nth prime to be
larger then 100");

printf("\n\nplease enter the Nth prime to be displayed, if you select 10,
the 10th, 20th, 30th... primes will be displayed.\n\nplease select a number
between 1 and 10,000, or 0 to exit\n");

scanf("%d",&nth);

if (!nth) return 0;

printf("please enter after how many numbers to pause. please select a number
between 2 and 10,000\n");

scanf("%d",&pause);

//************end collect info from user**************

//create and array to store the first 5000 primes:
long *prime = malloc(sizeof(long)*1000000);long counter=3;int flag =1;
*prime=1;*(prime+1)=2;*prime+2)=3; //set the first three primes
printf("\n\n\t\t---finished\n\n");
// i is the number that will be checked if it's a prime
//loop with i = 5 initially, add 2 to i every cycle,terminate if the counter
is greater then 10000000
for (long i=5;counter<1000000;i+=2,flag=1)
{
//check all primes that satisfy sqrt(i) >= prime
for (long j=2;*(prime+j)<long(sqrt(double(i))+1);j++)
{
if (i%*(prime+j)==0)//i is not a prime, go back to the first loop
{
flag=0;
break;
}
}

// now we know that i is a prime (since it's not divisible by any prime
that
( root(i) >= prime )

if (flag)
{
*(prime+counter)=i;
counter++;
if(counter%nth==0) printf("\t%ld",i);
if (counter%(nth*pause)==0) scanf("%*c");
flag=0;
}
else
continue;
}//end for loop
free(primes);
printf("\n\n***************************finished******************\n\n);
scanf("%*c");
return 0;
}
/**************************

//code to store the first 1000000 primes to a binary file:

//place the code at the END of the file

FILE *fp=fopen("15000pri.bin","r+b");
if (!fp) printf("unable to open file");
fwrite(prime,sizeof(prime)*1000000,1,fp);
if (fclose(fp))
printf("\n\nfile not closed\n\n");
else
printf("\n\nfile successfully closed\n\n");

//code to get the first 1000000 primes from the binary file:
//place the code right after the declaration of *prime
FILE *fp=fopen("15000pri.bin","r+b");
if (!fp) printf("unable to open file");
fread(prime,sizeof(prime)*1000000,1,fp);
if (fclose(fp))
printf("\n\nfile not closed\n\n");
else
printf("\n\nfile successfully closed\n\n");

//code to check the chances of a number being a prime when number%pause==0
// pause is a variable entered by the user
double chance = 1.0;
for (long k=1;k<1000000;k++)
{
if (k%(pause/1000)==0) printf("%ld ",*(prime+k));
chance -= double(1.0/double(*(prime+k)) * chance);
if (k%pause==0) {printf("\t%f\t%ld",chance,k); scanf("%*c"); }
}

//code to check primes within a range (maximum 200,000,000,000,000)

// you must have the first 1,000,000 primes loaded from a file or calculated
into the *prime
__int64 lower,upper;//non standard c. for the purpose of dealing with 64 bit
integers
//it can be changed to unsigned long, but then it will only support numbers
up to 4,294,967,296
// and change scanf("%I64") to scanf("%lu")

printf("\n\nplease enter the lower range.\n\nplease select a number between
5 and 10^12 (1, and 12 zeroes) , or 0 to exit\n");

scanf("%I64",&lower);
if (!nth) return 0;
printf("please enter the lower range.\n\nplease select a number between 5
and 10^12 (1, and 12 zeroes)");
fflush(stdin);
scanf("%I64",&upper);
if (upper<5 || upper>pow(10.0,12.0) || lower<5 || lower>pow(10.0,12.0))
{ printf("invalid range...exiting"); scanf("%*c); return 0; }

for (__int64 l=lower;l<=upper;l+=2,flag=1)
{
//check all primes that satisfy sqrt(i) >= prime
for (long m=2;prime[m]<long(sqrt(double(l))+1);m++)
{
if (l%prime[m]==0)//i is not a prime, go back to the first loop
{
flag=0;
break;
}
}

if (flag)
// now we know that i is a prime (since it's not divisible by any prime that
( root(i) >= prime )
{
printf("\t%I64",l);
flag=0;
}
else
continue;
}

//****************************/

 

[Paul Hsieh]

Sieve of Eratosthenes:

Make a list of all the integers less than or equal to n (and greater than
one). Strike out the multiples of all primes less than or equal to the
square root of n. Then the numbers that are left are the primes.

This discussion is probably better suited to something like comp.programming.
They are not much into algorithms or non-C related subjects at all around here.
But in any event, here's a nice little Sieve of Eratosthenes for you:

#define QF_SIEVE_SIZE (1024*1024)
static unsigned int qfSieve[QF_SIEVE_SIZE];
#define qfsIdx(x) ((x) >> 6)
#define qfsBit(x) (1 << (((x) & 63) >> 1))

/* You need to call this before calling the function below */

static void initQFSieve (void) {
int i, j, p;
for (i=0; i < QF_SIEVE_SIZE; i++) qfSieve = 0;
qfSieve[0] = 1;
for (p=3; p < (QF_SIEVE_SIZE * 64); p += 2) {
if ((qfSieve[qfsIdx (p)] & qfsBit (p)) != 0) continue;
j = p + p;
for (i = j + p; i < (QF_SIEVE_SIZE * 64); i += j) {
qfSieve[qfsIdx (i)] |= qfsBit (i);
}
}
}

enum QPT_result {
QPT_COMP = 0,
QPT_PRIME = 1,
QPT_DUNNO = 2
};

/* Test for evenness, equal to 2 or 3, otherwise the sieve of eratosthenes */

enum QPT_result quickPrimeTest (unsigned int l) {
if (l - 2 < 2) return QPT_PRIME;
if ((l & 1) == 0) return QPT_COMP;
if (l >= (QF_SIEVE_SIZE * 64)) return QPT_DUNNO;
if ((qfSieve[qfsIdx (l)] & qfsBit (l)) == 0) return QPT_PRIME;
return QPT_COMP;
}

You can find a more generic prime testing algorithm that handles all positive
singed numbers up to 32 bits in length in reasonable time, with reasonable
resources here:

http://www.pobox.com/~qed/32bprim.c

 

[Richard Heathfield]

Paul Hsieh wrote:

You can find a more generic prime testing algorithm that handles all
positive singed numbers up to 32 bits in length in reasonable time, with
reasonable resources here:

http://www.pobox.com/~qed/32bprim.c

Just like your line-reading code, this didn't compile:

gcc -g -W -Wall -ansi -pedantic -o foo foo.c -lm
foo.c: In function 'mulMod':
foo.c:91: '__int64' undeclared (first use in this function)
foo.c:91: (Each undeclared identifier is reported only once
foo.c:91: for each function it appears in.)
foo.c:91: parse error before 'a'
foo.c:94: 'a' undeclared (first use in this function)
foo.c:94: parse error before 'x'
foo.c:94: parse error before 'y'
foo.c:90: warning: unused parameter 'x'
foo.c:90: warning: unused parameter 'y'
foo.c:97: warning: control reaches end of non-void function
foo.c: In function 'powMod':
foo.c:107: warning: comparison between signed and unsigned
foo.c: In function 'SPPTestBase':
foo.c:130: warning: unused variable 'in'
foo.c: In function 'main':
foo.c:173: warning: unused parameter 'argc'
foo.c:173: warning: unused parameter 'argv'
make: *** [foo] Error 1

 

[Arthur J. O'Dwyer]

hi all

I'm a newbie to this group. my apologies if I break any rules.

Yes, but not quite as egregiously. Please don't change the subject
line of an old thread unless you are adding an [OT] flag or forking
a new discussion topic. Please try as hard as you can to write
properly capitalized and grammatical English, as we have many non-
native speakers of English here. And lastly, please please *please*
don't post unindented code that looks like trash and doesn't even
compile! See below.

I've wrote a simple program to find the first 1,000,000 primes, and to find
all primes within any range (up to 200 * 10^12)

it's pretty efficient, it took 15 minutes to compute the first 1,000,000
primes.

That *sounds* slow, but it obviously depends on your system.

I would like to here your opinion about it
I sincerely apologise for not following the rules last time.
and I would really appreciate RELEVANT responses,
p.s. I'm not a mathematician, in fact, my math level is primary school
(hardly).

If you're looking for good algorithms, try comp.programming.
If you want good C criticism, you'd better format your code before
you try posting it here again. If it doesn't compile (as yours
doesn't, due to incomplete string literals and badly wrapped comment
text), I won't explain what's wrong with it. And if I can't even
*read* it (as I can't yours, due to your lack of indentation and
terrible use of whitespace), then I won't even bother to fix the
mistakes that make it not compile.

printf("\t***WELCOME***\nthis program displays all prime numbers up to about
2 billion\nsince the output process takes a lot of resources,if you wish to
display large numbers, it is recommended that you set the Nth prime to be
larger then 100");

Line breaks are significant in C. Fix your string.

long *prime = malloc(sizeof(long)*1000000);long counter=3;int flag =1;

Line breaks are significant to your users, also. Fix your
declarations so that they're readable. Also note the bad use
of sizeof(long) in place of sizeof *prime.

*prime=1;*(prime+1)=2;*prime+2)=3; //set the first three primes

This line just plain isn't C. Also note that // comments are new
in C99, and IMHO should have been deprecated anyway.

is greater then 10000000

This line isn't C either.

//check all primes that satisfy sqrt(i) >= prime
for (long j=2;*(prime+j)<long(sqrt(double(i))+1);j++)

This line isn't C either. The long(...) syntax looks like old-style
C++, though. Also, do you have some personal vendetta against the
[] subscripting operator? *(prime+j) == prime[j].

( root(i) >= prime )

This line is going to get you some funny messages from the compiler,
too.

if (counter%(nth*pause)==0) scanf("%*c");

This is not the preferred way to discard a single character from
stdin. Write getchar(); if that's what you mean. Otherwise, write

while (getchar() != '\n') continue;

or something similar.

//code to store the first 1000000 primes to a binary file:

//place the code at the END of the file

Didn't you just close 'main'? You can't put executable code at
file scope; it won't compile. And you meant to open 'fp' for
writing ("wb") at this point, no doubt.

fwrite(prime,sizeof(prime)*1000000,1,fp);

fwrite(prime, 1000000, sizeof *prime, fp);

fread(prime,sizeof(prime)*1000000,1,fp);

fread(prime, 1000000, sizeof *prime, fp);

fflush(stdin);

Undefined behavior. Write scanf("%*[^\n]\n"); if that's what
you mean.

for (__int64 l=lower;l<=upper;l+=2,flag=1)

Please don't use 'l' as a variable name in Usenet-posted code.
There's a good reason why not, and I will give you 1 guess.

printf("\t%I64",l);

Try not to use tabs in your output. Ever. Because it makes your
output look silly when the user has his terminal configured slightly
differently from how you have *your* terminal configured. And
because in general, you're just using '\t' as an obfuscation for
' ' anyway. Do you think the backslash makes it look cooler
or something?

//****************************/

Finally, this comment style will definitely confuse your maintenance
programmers, because it means *slightly* different things in C89 and
C99. Stick to a comment style that either (1) works in both languages,
or (2) fails spectacularly in C89. Don't mix the two unless you want
frustrated users who can't understand why the compiler is complaining
about /'s not being a unary operator.

Format your code properly, fix these bugs, and submit it again.
Then I bet you'll get some real help with whatever problems you're
having with the program itself.

HTH,
-Arthur

 

[Arthur J. O'Dwyer]

Just like your line-reading code, this didn't compile:

gcc -g -W -Wall -ansi -pedantic -o foo foo.c -lm
foo.c: In function 'mulMod':
foo.c:91: '__int64' undeclared (first use in this function)

To Richard: Note that Paul did address this problem in a
comment buried in the code. If I were to use his code in a
project, I'd make sure to read all the comments before starting
to compile it.

To Paul: IMHO it would be better to write the *portable*
version of the code by default (e.g., use 'long int' instead of
'__int64'), and then have a comment buried in the code (or
preferably at the top of the file) telling the sophisticated
source diver what to do if he wants better performance on a
Microsoft compiler. This way, people can use the code "out of
the box," like Richard tried to do, and it will work -- but
those who need the performance can make minor adjustments and
get their performance, too.
Best of both worlds: set up a 'typedef' at the top of the
file, with an explanatory comment, and let it default to the
most portable setting possible.

-Arthur

 

[Sidney Cadot]

Paul Hsieh wrote:

You can find a more generic prime testing algorithm that handles all
positive singed numbers up to 32 bits in length in reasonable time, with
reasonable resources here:

http://www.pobox.com/~qed/32bprim.c

Just like your line-reading code, this didn't compile:

gcc -g -W -Wall -ansi -pedantic -o foo foo.c -lm
foo.c: In function 'mulMod':
foo.c:91: '__int64' undeclared (first use in this function)
foo.c:91: (Each undeclared identifier is reported only once
foo.c:91: for each function it appears in.)
foo.c:91: parse error before 'a'
foo.c:94: 'a' undeclared (first use in this function)
foo.c:94: parse error before 'x'
foo.c:94: parse error before 'y'
foo.c:90: warning: unused parameter 'x'
foo.c:90: warning: unused parameter 'y'
foo.c:97: warning: control reaches end of non-void function
foo.c: In function 'powMod':
foo.c:107: warning: comparison between signed and unsigned
foo.c: In function 'SPPTestBase':
foo.c:130: warning: unused variable 'in'
foo.c: In function 'main':
foo.c:173: warning: unused parameter 'argc'
foo.c:173: warning: unused parameter 'argv'
make: *** [foo] Error 1

....You probably just forgot the flag to enable the experimental
"operator introduction" feature.

Just venting some frustration....

Best regards, Sidney

 

[someone else]

This discussion is probably better suited to something like comp.programming.
They are not much into algorithms or non-C related subjects at all around here.
But in any event, here's a nice little Sieve of Eratosthenes for you:

<snip>
I tried the code from the link http://www.pobox.com/~qed/32bprim.c
and indeed it's a little faster then mine (10%-15%)
but it's pretty comlicated and requires a good understanding of both math
and c, and like you said, is better suited to comp.programming, and unestly,
i did not understand all of it.

i truncated my code to show you how simple it is:

/* just remember to include math.h and stdio.h */
long *prime = malloc(sizoof(long)*1000000);long counter=3;int flag =1;
prime[0]=1;prime[1]=2;prime[2]=3;
for (long i=5;counter<100000000;i+=2,flag=1) {
/*check all primes that satisfy sqrt(i) >= prime */
for (long j=2;prime[j]<long(sqrt(double(i))+1);j++) {
if (i%prime[j]==0) { /* i is not a prime, go back to the first loop
*/
flag=0;
break;
}
}

if (flag) {
// now we know that i is a prime (since it's not divisible by any prime
that ( root(i) >= prime )
if (counter<1000000) {prime[counter]=i; counter++; }
printf("\t%ld",i);
flag=0;
}
else
continue;
}
printf("\n\n*****************finished***********\n\npress any key to exit");
getchar();

 

[glen herrmannsfeldt]

Arthur J. O'Dwyer wrote:

(snip)

To Richard: Note that Paul did address this problem in a
comment buried in the code. If I were to use his code in a
project, I'd make sure to read all the comments before starting
to compile it.

It just occurred to me how nice it would be to have a statement,
probably for the preprocessor, that would cause a message to
be printed when it compiled. Such warnings could then be
put in that way.

The IBM S/360 Assemblers, and successors, have an opcode to
print out a message at assembly time, mostly so that macro
expansions can print error messages.

It would seem that preprocessed C could also have messages
that need to be printed.

#ifdef NUM<0
#note Oops, NUM is less than zero!
#else
int x[NUM];
#endif

-- glen

 

[Dik T. Winter]

> It would seem that preprocessed C could also have messages
> that need to be printed.
>
> #ifdef NUM<0
> #note Oops, NUM is less than zero!
> #else
> int x[NUM];
> #endif

#if NUM<0
#error Oops, NUM is less than zero!
#else
int x[NUM];
#endif

 

[Paul Hsieh]

someone says...

<snip>
I tried the code from the link http://www.pobox.com/~qed/32bprim.c
and indeed it's a little faster then mine (10%-15%)

Well it includes the Sieve of Eratosthenes within the source. It also includes
a kind of "parallel small prime divisor test" (using gcd!) before I bring out
the big guns (Strong-Pseduo-Prime test.) Given that you don't seem to care
about memory usage, you can easily crank the performance for small primes such
as all those < 10^6 by simply increasing the size of the sieve (QF_SIEVE_SIZE)
as desired.

but it's pretty comlicated and requires a good understanding of both math
and c, and like you said, is better suited to comp.programming, and unestly,
i did not understand all of it.

Well, completely understanding it may be a tall order. But I give references
for the math-related algorithms, so you can study those at your leisure. What
is worth-while *understanding* in my algorithm is that it takes roughly the
same amount of time (once it gets past the sieve, and trivial divisors, I mean)
regardless of the size of the input.

Your algorithm is a fine, simplistic algorithm, however it really only works
because you determine the entire sequence of primes one after another. But
for longer and longer sequence of primes it will get slower and slower and
you'll run out of memory sooner or later.

 

[Paul Hsieh]

(e-mail address removed) says:

To Paul: IMHO it would be better to write the *portable*
version of the code by default (e.g., use 'long int' instead of
'__int64'), and then have a comment buried in the code (or
preferably at the top of the file) telling the sophisticated
source diver what to do if he wants better performance on a
Microsoft compiler. This way, people can use the code "out of
the box," like Richard tried to do, and it will work -- but
those who need the performance can make minor adjustments and
get their performance, too.

Well, as you can imagine my considerations of whether or not Richer Heathfield
can find some violation of the ANSI standard in my code is not exactly high on
my todo list. I've got navel lint that needs sorting.

I am not typically prone to writing non-portable code just for the fun of it.
Using __int64 is not a "performance concern" (it rarely is) -- its a
functionality consideration. Using "long int" which may be implemented by a
compiler to be 32 bits, is not an acceptable compromise -- it would reduce the
correctness of the algorithm to a range of <65536 (the Sieve of Eratosthenes,
by itself can easily go beyond this.) This is the whole "widening multiply"
thing all over again (which I won't regurgitate here, as it always seems to
take 10 posts of explanation before people "get it".)

But since you asked so nicely, I have made a correction which uses *doubles* in
place of __int64 if compiled with an unrecognized compiler. This allows it to
work for inputs that are up to 26 bits on most typical machines with a 64 bit
IEEE-754 double implementation (it would also work for all 32bits for typical
80+ bit FP implementations). And I threw in some "guesswork code" about how it
might work on gcc.

So its now more "portable", but that won't help it be any more correct on
platforms without a 64 bit integer (or 80 bit FP.)

 

[glen herrmannsfeldt]

It would seem that preprocessed C could also have messages
that need to be printed.

#ifdef NUM<0
#note Oops, NUM is less than zero!
#else
int x[NUM];
#endif

#if NUM<0
#error Oops, NUM is less than zero!
#else
int x[NUM];
#endif

Not quite what I wanted. That seems to cause a fatal error.

I suppose the example isn't very good, but there are cases when
a warning, or even less. Maybe just a reminder to the person
compiling the program.

-- glen