Velocity Reviews > Prime number algorithm in C

# Prime number algorithm in C

Cmorriskuerten
Guest
Posts: n/a

 11-17-2003
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
*/
int is_prime_number(int n)
{
long c;

if (n < 2) return FALSE;

for (c = 2; c < n; c++)
{
if ((n % c) == 0) return FALSE;
}
return TRUE;
}

Tia,

Chris

Sheldon Simms
Guest
Posts: n/a

 11-17-2003
On Mon, 17 Nov 2003 16:28:10 +0000, Cmorriskuerten wrote:

> 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
> */
> int is_prime_number(int n)
> {
> long c;
>
> if (n < 2) return FALSE;
>
> for (c = 2; c < n; c++)
> {
> if ((n % c) == 0) return FALSE;
> }
> return TRUE;
> }

It would be better to ask questions like this in comp.programming
next time.

However, it does appear that the function would work. It would be
quite slow, though.

Christopher Benson-Manica
Guest
Posts: n/a

 11-17-2003
osmium <(E-Mail Removed)> spoke thus:

> You could improve it a lot by avoiding the test for even numbers except 2 by
> changing the increment. Also, once you have reached the square root of n,
> any further testing is doomed to failure so you might as well stop there.
> But if you insert the square root test in the obvious way you are depending
> on the compiler to be smart enough to optimize it away. So it *could*
> actually get slower.

He could stop at n/2 and still cut the run time in half...

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.

James Hu
Guest
Posts: n/a

 11-17-2003
On 2003-11-17, Christopher Benson-Manica <(E-Mail Removed)> wrote:
> osmium <(E-Mail Removed)> spoke thus:
>
>> Also, once you have reached the square root of n, any further testing
>> is doomed to failure so you might as well stop there. But if you
>> insert the square root test in the obvious way you are depending on
>> the compiler to be smart enough to optimize it away.

>
> He could stop at n/2 and still cut the run time in half...

In C classic:

#define leq_sqrt(v, n) (v <= n/v)

In C99:

inline _Bool leq_sqrt(unsigned v, unsigned n) { return v <= n/v; }

<ot>
Why stopping at sqrt is enough:

Property:
a, b, n non-negative integers and a*b == n and a <= b
then
a <= sqrt(n) and b >= sqrt(n)

Proof:
Case 1: a == sqrt(n)
if a == sqrt(n) then b == sqrt(n)

Case 2: a != sqrt(n)
if a < sqrt(n) then
a*b < sqrt(n)*b, but since a*b == n, then
n < sqrt(n)*b, implies
sqrt(n) < b, in other words
b > sqrt(n)

Assume a > sqrt(n). Then using similar logic to above,
we arrive at b < sqrt(n). This implies that b < a.
This is a contradiction of a <= b.

There are no other cases to consider.

Thus, we have shown a*b == n and a <= b implies
a <= sqrt(n) and b >= sqrt(n)
for non-negative integers a, b and n.

QED.
</ot>

-- James

Dan Pop
Guest
Posts: n/a

 11-17-2003
In <(E-Mail Removed)> http://www.velocityreviews.com/forums/(E-Mail Removed) (Cmorriskuerten) writes:

>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
>*/
>int is_prime_number(int n)
>{
> long c;
>
> if (n < 2) return FALSE;
>
> for (c = 2; c < n; c++)
> {
> if ((n % c) == 0) return FALSE;
> }
> return TRUE;
>}

Last time I checked, 2 was a prime number, but your function claims
otherwise.

Apart from that, both the "algorithm" and the implementation are
incredibly naive. You should have certainly spent more time designing
the algorithm, rather than simply using a stupid, brute force approach.

Implementation-wise: if n is int, what's the point in making c long?
Do you really want your function to run as slow as possible?

On the algorithm side: after testing divisibility by 2, there is no
point in checking divisibility by any other even number. And there is
no point in checking any number up to n - 1 as a possible divisor, you
can safely stop at sqrt(n).

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: (E-Mail Removed)

Dan Pop
Guest
Posts: n/a

 11-17-2003
In <bpb3ek\$6c2\$(E-Mail Removed)> I wrote:

>In <(E-Mail Removed)> (E-Mail Removed) (Cmorriskuerten) writes:
>
>>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
>>*/
>>int is_prime_number(int n)
>>{
>> long c;
>>
>> if (n < 2) return FALSE;
>>
>> for (c = 2; c < n; c++)
>> {
>> if ((n % c) == 0) return FALSE;
>> }
>> return TRUE;
>>}

>
>Last time I checked, 2 was a prime number, but your function claims
>otherwise.

Please ignore this comment. The case when n == 2 is properly handled,
because the for loop is skipped.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: (E-Mail Removed)

osmium
Guest
Posts: n/a

 11-17-2003
Cmorriskuerten writes:

> 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
> */
> int is_prime_number(int n)
> {
> long c;
>
> if (n < 2) return FALSE;
>
> for (c = 2; c < n; c++)
> {
> if ((n % c) == 0) return FALSE;
> }
> return TRUE;
> }

The logic looks OK to me, but the acid test is to try it. I mention logic
because I don't know how TRUE and FALSE obtained their values in this
snippet. I am not fond of the mix of int and long. I don't like the name.
We already *know* it's a number. How about is_prime? Why 'c'? Candidate?

You could improve it a lot by avoiding the test for even numbers except 2 by
changing the increment. Also, once you have reached the square root of n,
any further testing is doomed to failure so you might as well stop there.
But if you insert the square root test in the obvious way you are depending
on the compiler to be smart enough to optimize it away. So it *could*
actually get slower.

Lorenzo J. Lucchini
Guest
Posts: n/a

 11-18-2003
(E-Mail Removed) (Dan Pop) wrote in message news:<bpb3ek\$6c2\$(E-Mail Removed)>...
> In <(E-Mail Removed)> (E-Mail Removed) (Cmorriskuerten) writes:
>
>> [prime number algorithm]

>
> [snip]
>
> On the algorithm side: after testing divisibility by 2, there is no
> point in checking divisibility by any other even number.

And after testing divisibility by 3, there is no point in checking
divisibility by any other multiple of 3.
Sure, it's easier to put your sentence about 2 in an algorithm than it
is to put mine about 3 in one; but personally, I would decide to
either live with an algorithm that tests for every positive integer up
to sqrt(n) or - after I realize I don't need to test for multiples of
numbers I've already tested for - devise another algorithm that takes
this into account.
Don't you think simply incrementing the counter by 2 instead of by 1
is in a way a micro-optimization?

> [snip]

by LjL
(E-Mail Removed)

Dan Pop
Guest
Posts: n/a

 11-19-2003
In <(E-Mail Removed) > (E-Mail Removed) (Lorenzo J. Lucchini) writes:

>(E-Mail Removed) (Dan Pop) wrote in message news:<bpb3ek\$6c2\$(E-Mail Removed)>...
>> In <(E-Mail Removed)> (E-Mail Removed) (Cmorriskuerten) writes:
>>
>>> [prime number algorithm]

>>
>> [snip]
>>
>> On the algorithm side: after testing divisibility by 2, there is no
>> point in checking divisibility by any other even number.

>
>Don't you think simply incrementing the counter by 2 instead of by 1
>is in a way a micro-optimization?

Nope, I don't: it accelerates the *algorithm*, not the implementation,
by a factor of 2. If this is a micro-optimization in your book, I would
be really interested to know what counts as a real optimisation to you.

Micro-optimisations don't touch the algorithm, they merely accelerate
its implementation by taking advantage of certain properties of the
implementation and/or the underlying hardware. Replacing a multiplication
by a power of 2 with a left shift is a micro-optimisation if the
latter is faster and if the compiler is not smart enough to do the
replacement itself.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: (E-Mail Removed)

Lorenzo J. Lucchini
Guest
Posts: n/a

 11-19-2003
(E-Mail Removed) (Dan Pop) wrote in message news:<bpfi2g\$8up\$(E-Mail Removed)>...
> In <(E-Mail Removed) > (E-Mail Removed) (Lorenzo J. Lucchini) writes:
>
> >(E-Mail Removed) (Dan Pop) wrote in message news:<bpb3ek\$6c2\$(E-Mail Removed)>...
> >> In <(E-Mail Removed)> (E-Mail Removed) (Cmorriskuerten) writes:
> >>
> >>> [prime number algorithm]
> >>
> >> [snip]
> >>
> >> On the algorithm side: after testing divisibility by 2, there is no
> >> point in checking divisibility by any other even number.

> >
> >Don't you think simply incrementing the counter by 2 instead of by 1
> >is in a way a micro-optimization?

>
> Nope, I don't: it accelerates the *algorithm*, not the implementation,
> by a factor of 2. If this is a micro-optimization in your book, I would
> be really interested to know what counts as a real optimisation to you.

I stand corrected. However, I must say that personally I would still
make a choice between testing for every number and only testing for
those numbers that are not multiples of a number I've already tested
for.
Testing for every number says "I want to make the algorithm as
straight-forward as possible".
Testing for non-multiples of tested numbers says "I want to make the
algorithm good"
Testing for every number except for multiples of two says "At the
beginning I thought I would need to test for every number; then I
realized I did not need to test for multiples of two; who knows, maybe
one day I'll even realize I don't need to test for multiples of *any*

At least that's what I'd tend to deduce after reading the three
different algorithms.

> [snip]

by LjL
(E-Mail Removed)