473,842 Members | 1,887 Online

# Prime number algorithm in C

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
Nov 13 '05
32 76467
Eric Sosman wrote:
James Hu wrote:
On 2003-11-20, Eric Sosman <Er*********@su n.com> wrote:
James Hu wrote:
> [...]
> #define ISQRT_G_1(N) (N>>((sizeof(N) *CHAR_BIT)/2))
> #define ISQRT_G_2(N) ((ISQRT_G_1(N)+ N/ISQRT_G_1(N))/2)
> #define ISQRT_G_3(N) ((ISQRT_G_2(N)+ N/ISQRT_G_2(N))/2)
> #define ISQRT_G_4(N) ((ISQRT_G_3(N)+ N/ISQRT_G_3(N))/2)
> #define ISQRT_G_5(N) ((ISQRT_G_4(N)+ N/ISQRT_G_4(N))/2)
> #define ISQRT_G_6(N) ((ISQRT_G_5(N)+ N/ISQRT_G_5(N))/2)
> #define ISQRT(N) ISQRT_G_6(N)

This isn't going to work very well for N less than
the square root of its type's maximum value: the initial
guess will be zero, and after that ...

I wrote that macro specifically to find the square root of
ULONG_MAX.

Aha. I hadn't realized the limited intent; sorry.

If you are willing to settle for the root of (<T>_MAX + 1), which
must be of the form 2**n, simpler methods are available. At worst
the root of 2 may be involved, for n odd.

--
Chuck F (cb********@yah oo.com) (cb********@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!
Nov 13 '05 #21
On Mon, 17 Nov 2003 11:46:08 -0600, James Hu <jx*@despammed. com>
wrote:
On 2003-11-17, Christopher Benson-Manica <at***@nospam.c yberspace.org> wrote:
osmium <r1********@com cast.net> 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)

Add parens ( (v) <= (n)/(v) ) to be safe in all uses.
In C99:

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

Or (in both versions) v * v <= n, which faster on nearly all
platforms, often much faster.

Or, less general, strength-reduce vsquared in the loop by adding 2*v-1
for each increment, or 2*(v-1)+2*v-2 aka 4*v-4 for increment-by-2.

- David.Thompson1 at worldnet.att.ne t
Nov 13 '05 #22
On 2003-11-22, Dave Thompson <da************ *@worldnet.att. net> wrote:
On Mon, 17 Nov 2003 11:46:08 -0600, James Hu <jx*@despammed. com>
wrote:

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

Add parens ( (v) <= (n)/(v) ) to be safe in all uses.

Yes, thanks.
In C99:

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

Or (in both versions) v * v <= n, which faster on nearly all
platforms, often much faster.

But this is prone to overflow.

-- James
Nov 13 '05 #23
In <3F************ ***@yahoo.com> CBFalconer <cb********@yah oo.com> writes:
Eric Sosman wrote:
James Hu wrote:
> On 2003-11-20, Eric Sosman <Er*********@su n.com> wrote:
> > James Hu wrote:
> >> [...]
> >> #define ISQRT_G_1(N) (N>>((sizeof(N) *CHAR_BIT)/2))
> >> #define ISQRT_G_2(N) ((ISQRT_G_1(N)+ N/ISQRT_G_1(N))/2)
> >> #define ISQRT_G_3(N) ((ISQRT_G_2(N)+ N/ISQRT_G_2(N))/2)
> >> #define ISQRT_G_4(N) ((ISQRT_G_3(N)+ N/ISQRT_G_3(N))/2)
> >> #define ISQRT_G_5(N) ((ISQRT_G_4(N)+ N/ISQRT_G_4(N))/2)
> >> #define ISQRT_G_6(N) ((ISQRT_G_5(N)+ N/ISQRT_G_5(N))/2)
> >> #define ISQRT(N) ISQRT_G_6(N)
> >
> > This isn't going to work very well for N less than
> > the square root of its type's maximum value: the initial
> > guess will be zero, and after that ...
>
> I wrote that macro specifically to find the square root of
> ULONG_MAX.

Aha. I hadn't realized the limited intent; sorry.

If you are willing to settle for the root of (<T>_MAX + 1), which
must be of the form 2**n, simpler methods are available. At worst
the root of 2 may be involved, for n odd.

Show us the code, as a constant expression that can be evaluated at
compile time.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Nov 13 '05 #24
Dan Pop wrote:

In <3F************ ***@yahoo.com> CBFalconer <cb********@yah oo.com> writes:
Eric Sosman wrote:
James Hu wrote:
> On 2003-11-20, Eric Sosman <Er*********@su n.com> wrote:
> > James Hu wrote:
> >> [...]
> >> #define ISQRT_G_1(N) (N>>((sizeof(N) *CHAR_BIT)/2))
> >> #define ISQRT_G_2(N) ((ISQRT_G_1(N)+ N/ISQRT_G_1(N))/2)
> >> #define ISQRT_G_3(N) ((ISQRT_G_2(N)+ N/ISQRT_G_2(N))/2)
> >> #define ISQRT_G_4(N) ((ISQRT_G_3(N)+ N/ISQRT_G_3(N))/2)
> >> #define ISQRT_G_5(N) ((ISQRT_G_4(N)+ N/ISQRT_G_4(N))/2)
> >> #define ISQRT_G_6(N) ((ISQRT_G_5(N)+ N/ISQRT_G_5(N))/2)
> >> #define ISQRT(N) ISQRT_G_6(N)
> >
> > This isn't going to work very well for N less than
> > the square root of its type's maximum value: the initial
> > guess will be zero, and after that ...
>
> I wrote that macro specifically to find the square root of
> ULONG_MAX.

Aha. I hadn't realized the limited intent; sorry.

If you are willing to settle for the root of (<T>_MAX + 1), which
must be of the form 2**n, simpler methods are available. At worst
the root of 2 may be involved, for n odd.

Show us the code, as a constant expression that can be evaluated at
compile time.

Adding the constant expression clause may be the rub, as offhand I
do not know of any way of evaluating n above. Well, possibly a
table, such as:

#if INT_MAX == 32767
# define n 16
#elif INT_MAX == 65536
# define n 17
.....

which doesn't appear overly attractive to me. :-)

Apropos to other arguments going on around here, things might have
been simpler if the maximum bit weight (n above) had been
specified as an exponent of two, rather than the <T>_MAX values.
i.e.

#define INT_MAX_BIT 30

etc. This also leaves no holes and ambiguity to foster arguments
:-)

--
Chuck F (cb********@yah oo.com) (cb********@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!
Nov 13 '05 #25
In <3F************ **@yahoo.com> CBFalconer <cb********@yah oo.com> writes:
Adding the constant expression clause may be the rub, as offhand I
do not know of any way of evaluating n above. Well, possibly a
table, such as:

#if INT_MAX == 32767
# define n 16
#elif INT_MAX == 65536
# define n 17
.....

which doesn't appear overly attractive to me. :-)

And doesn't appear correct at all to me. Are you sure you're familiar
with the powers of two? ;-)

BTW, if you go this way, you can define the square root directly, instead
of n.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Nov 13 '05 #26
Dan Pop wrote:
CBFalconer <cb********@yah oo.com> writes:

.... snip ...

#if INT_MAX == 32767
# define n 16
#elif INT_MAX == 65536
# define n 17
.....

which doesn't appear overly attractive to me. :-)

And doesn't appear correct at all to me. Are you sure you're
familiar with the powers of two? ;-)

0.0002% is well within the expected experimental error :-)

--
Chuck F (cb********@yah oo.com) (cb********@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!
Nov 13 '05 #27
In <3F************ ***@yahoo.com> CBFalconer <cb********@yah oo.com> writes:
Dan Pop wrote:
CBFalconer <cb********@yah oo.com> writes:

... snip ...
>
> #if INT_MAX == 32767
> # define n 16
> #elif INT_MAX == 65536
> # define n 17
> .....
>
>which doesn't appear overly attractive to me. :-)

And doesn't appear correct at all to me. Are you sure you're
familiar with the powers of two? ;-)

0.0002% is well within the expected experimental error :-)

Still missing the point. Your worst error above is 6.66% ;-)

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Nov 13 '05 #28
On Sat, 22 Nov 2003 00:11:22 -0600, James Hu <jx*@despammed. com>
wrote:
On 2003-11-22, Dave Thompson <da************ *@worldnet.att. net> wrote:
On Mon, 17 Nov 2003 11:46:08 -0600, James Hu <jx*@despammed. com>
wrote: <snip>
inline _Bool leq_sqrt(unsign ed v, unsigned n) { return v <= n/v; }

Or (in both versions) v * v <= n, which faster on nearly all
platforms, often much faster.

But this is prone to overflow.

In general yes, though not if you are running the loop upwards (as was
the previous-post case) and n is not almost UINT_MAX (which caveat I
didn't state). But you can add a check for v <= sqrt_of_uint_ma x,
which is actually a compile-time constant although it seems difficult
to portably write it so, and I bet it's still faster than divide.

- David.Thompson1 at worldnet.att.ne t
Nov 13 '05 #29
On 2003-11-27, Dave Thompson <da************ *@worldnet.att. net> wrote:
On Sat, 22 Nov 2003 00:11:22 -0600, James Hu <jx*@despammed. com>
wrote:
On 2003-11-22, Dave Thompson <da************ *@worldnet.att. net> wrote:
> On Mon, 17 Nov 2003 11:46:08 -0600, James Hu <jx*@despammed. com>
> wrote:
>> ... v <= n/v ...
>>
> ... v * v <= n ...

But this is prone to overflow.

In general yes, though not if you are running the loop upwards (as was
the previous-post case) and n is not almost UINT_MAX (which caveat
I didn't state). But you can add a check for v <= sqrt_of_uint_ma x,
which is actually a compile-time constant although it seems difficult
to portably write it so, and I bet it's still faster than divide.

I don't doubt multiplication is faster than division on most platforms.
But, I tend to first write code that I know will work first. I've been
bitten by multiplication overflow too many times, I'm afraid.

-- James
Nov 13 '05 #30

This thread has been closed and replies have been disabled. Please start a new discussion.