This program finds prime numbers with Euler's formula: n^2 + n +
41. It finds the primes in a range of n and calculates the
percentage of primes in the range.It behaves very strangely. All
n's < 40 produce primes and for all ranges with the upper limit <
40 the program produces the correct output. But when the upper
bound of the range is > 39 the program outputs 0.00 as the
percentage of primes even though the values for n's tested and
primes found are correct. I would greatly appreciate it if a C
guru could tell me why this is happening. Try inputs of 0 39,
then, say, 0 50.

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define COEFF 41
int ptest(int p);

int main(int argc, char *argv[])
{
int start, stop, count, range, n, p;
double power, percent;

if(argc != 3)exit(EXIT_FAILURE);
start = atoi(argv[1]);
stop = atoi(argv[2]);
count = 0;
for(n = start; n <= stop; ++n)
{
power = pow(n, 2);
p = power + n + COEFF;
if(ptest(p))
{
++count;
printf("%d %d\n", n, p);
}
}
range = (stop - start) + 1;
percent = (count / range) * 100;
printf("\nprimes: %d\n", count);
printf("\nnumbers: %d\n", range);
printf("\npercent: %.2f\n", percent);
return 0;
}

int ptest(int p)
{
int n, pflag = 0;
for(n = 2; n < p; ++n)
if(p % n == 0) pflag = 1;

return (pflag == 0);
}

BTW, this program was also written in Python and VB with
precisely the same logic and had no problems. Sometimes C can be
very frustrating. :-(

In article <4047ACFB.9020706@email.net>, Elliot Marks <emarks@email.net> wrote:
count and range are both ints. Thus count / range gives zero if count
is less than range.

Gerry Quinn
--
http://bindweed.com
Screensavers, Games, Kaleidoscopes
Download free trial versions

On Thu, 4 Mar 2004 22:26:06 UTC, Elliot Marks <emarks@email.net> wrote:

Elliot,

C is a bit like FORTRAN in that how you define the variables
can make a big difference on the results. The general percentage
of primes goes down as your range increases. At some point this
approaches 1% and crosses down to 0%.

Your line that calculates percent given the count and range
is performing integer arithmetic. Since you appear to want the
accuracy of double precision floating point, we need to make
a few changes. Try the following line instead.

percent = ((count * 1.0) / (range * 1.0)) * 100.0;

Multiplying by 1.0 (real, not integer) forces count and range
to become reals before and during the division. This can be
optimized out to integer though if percent was declared as an int.
Sometimes such calculations require explicit definition as doubles
before making such calculations. 100.0 is a real value; 100 is an int.
The idea is to keep C thinking that all the intermediate values should
be doubles and to preserve that as the final result.

percent = count * 100 / range; // better but is all integer; rounds to zero
a bit later

percent = count * 100.0 / range; // may be acceptable

My compiler isn't working and I'm not going to transfer to another
machine to do a test compile. The last line above may be a simpler
solution. Working from left to right, we have a real divided by
integer which should promote to real because the desired result (percent)
is a real. Some extra type caasting may be required to insure that
the last line always gives the desired result.

Good luck,

David

Elliot Marks <emarks@email.net> wrote:
Other people already told you about the problem with the integer
division. But your test for primeness is really doing much too
much work. First of all, you can stop checking immediately when
you find that p % n is 0, you don't have to do all the remaining
tests, since you then already know that the number isn't prime.
So a slightly better version would be

int ptest( int p )
{
int n;
for ( n = 2; n < p; ++n )
if ( p % n == 0 )
return 0;
return 1;
}

But then you also don't have to check for divisions by even numbers,
just test if the number is even (in which case it's no prime anyway)
and then test only divisions by odd numbers like

int ptest( int p )
{
int n;

if ( p % 2 == 0 )
return 0;

for ( n = 3; n < p; n += 2 )
if ( p % n == 0 )
return 0;
return 1;
}

Further, you also can stop testing if n gets larger than the square
root of p, so use something like

int ptest( int p )
{
int n;
int n_max = ( int ) sqrt( p );

if ( p % 2 == 0 )
return 0;

for ( n = 3; n <= n_max; n += 2 )
if ( p % n == 0 )
return 0;
return 1;
}

Please note that you may have to link against the math library to get
the sqrt() function. But it should speed up your program a bit;-)

Regards, Jens
--
\ Jens Thoms Toerring ___ Jens.Toerring@physik.fu-berlin.de
\__________________________ http://www.toerring.de

Jens.Toerring@physik.fu-berlin.de wrote:

Thanks to all for your replies. I am aware that the test for
primality is inefficient, but knowing that the numbers processed
in this little exercise will be very small, inefficiency was an
option. :-)

Elliot

Jens.Toerring@physik.fu-berlin.de wrote:

<snip>

Right.

Since when was 2 composite? :-)

if(p == 2)
return 1;

if(p % 2 == 0)
return 0;

Being paranoid and yet far too lazy to work out the math, I'd say

int n_max = 1 + sqrt(p);

just to be on the safe side.

--
Richard Heathfield : binary@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

Richard Heathfield <dontmail@address.co.uk.invalid> wrote:
Embarrissing;-) The only wriggle room I am left with is probably that it
was rather clear from the post that the test would only be applied to
numbers larger than 41. But I probably should stop following the
phycisists approach to prime numbers: All odd numbers are prime, 1 is
prime, 3 is prime, 5 is prime, 7 is prime, 9 is an experimental error,
11 is prime...

That's really better, mostly for a computational reason: sqrt( x * x )
with x being an integer can result in a number smaller than x (due to
floating point rounding errors), which then would be truncated to x - 1
by the cast to int. Thanks, Richard.

Regards, Jens
--
\ Jens Thoms Toerring ___ Jens.Toerring@physik.fu-berlin.de
\__________________________ http://www.toerring.de

Elliot Marks wrote:
In addition to the excellent comments already given, be wary of using
floating point for your integer calculations. The function pow() must
use transcendental functions to compute for the general case, which may
introduce a very small error in the result. If power were slightly less
than n^2, then the following assignment to p would result in an integer
one less than the correct value. The easiest way to fix this is simply
to use the expression

p = n * n + n + COEFF;

You could also use the floating point computation if you added a
rounding constant to avoid the truncation, but it isn't needed for this
use.

Thad

Richard Heathfield wrote:
Good point. In Jens's defense, within the context of the OP, all tested
numbers of the form n^2+n+41 were odd[1], of course, so it was a moot
point.

Thad

Thad Smith <thadsmith@acm.org> wrote in news:4048A4DB.E29CE276@acm.org:

Similarly, if you are terminating your test when the test value is the
square root of the tested value, you should not use the sqrt function.
Instead, if the test value is 'n', you should test
if ((n * n) <= p)

This allows all your computations to be integer computations.

Jim Rogers

James Rogers wrote:

<snip>
Better still, take the hit *once* on sqrt, and avoid a multiply in the loop.

(Well; *is* that better? Answer: use a profiler!)

--
Richard Heathfield : binary@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

James Rogers wrote:
<snip>
A small number of FP operations at the start may well be faster than
adding a multiply every pass... depending on the size of the primes
you're testing for and how slow sqrt() is on your platform.

--
Corey Murtagh
The Electric Monk
"Quidquid latine dictum sit, altum viditur!"

Corey Murtagh <emonk@slingshot.no.uce> wrote in
news:1078539594.508019@radsrv1.tranzpeer.net:

Don't forget the small but real overhead of converting between an
integer and a floating point value every loop iteration to perform
the comparison when using sqrt().

Jim Rogers

James Rogers schrieb:
You can convert the sqrt to integer outside of the loop; in fact I'd
expect the compiler to do this.

Michael
--
Feel the stare of my burning hamster and stop smoking!

In article <rOdGr40LMPU3-pn2-6x9qNfPeRDJV@localhost>, David wrote:
Keep it simple, please. As David correctly stated you are doing
integer division and multiplication when calculating the percentage
and it is converted to a double at the assignment.

You need to force the arithmetic into doubles earlier so either:
percent = 100.0L * count / range;
or
percent = ((double)count / range) * 100;

David's solution only forces the math into floats. The multiplications
by one are all misleading when someone is reading the code.

- AndrewN