473,842 Members | 1,887 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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.

Similar topics

36
8417
by: Dag | last post by:
Is there a python module that includes functions for working with prime numbers? I mainly need A function that returns the Nth prime number and that returns how many prime numbers are less than N, but a prime number tester would also be nice. I'm dealing with numbers in the 10^6-10^8 range so it would have to fairly efficient Dag
9
2718
by: Greg Brunet | last post by:
In doing some testing of different but simple algorithms for getting a list of prime numbers, I ended up getting some results that seem a bit contradictory. Given the following test program (testPrimes.py) with two algorithms that both check for primes by testing only odd numbers using factors up to the square root of the value, where Primes1 is based on all of the existing primes so far, and Primes2 is based on all odd numbers, I would...
5
2729
by: Rahul | last post by:
HI. Python , with its support of arbit precision integers, can be great for number theory. So i tried writing a program for testing whether a number is prime or not. But then found my function painfully slow.Here is the function : from math import sqrt def isPrime(x): if x%2==0 or x%3==0: return 0
11
5950
by: lostinpython | last post by:
I'm having trouble writing a program that figures out a prime number. Does anyone have an idea on how to write it? All I know is that n > 2 is prim if no number between 2 and sqrt of n (inclusivly) evenly divides n.
11
7167
by: don | last post by:
Ok, this is a homework assignment, but can you help me out anyway...... I need a routine for figuring out if a number inputted by the user is a prime number or not...... all I'm asking for is Not the exact code ( well maybe a little) but the logic or algorithm to tell whether or not a number is prime....
3
2759
by: ckroom | last post by:
Anyone knows a good algorithm to get the next prime of a number n? prime = nextprime( n ); It's for some stuff about double rehashing, thanks. -- ckroom http://nazaries.net/~ckroom
20
6833
by: Tuvas | last post by:
I have made and recently posted a libary I made to do Modular Arithmetic and Prime numbers on my website at http://www.geocities.com/brp13/Python/index.html . I am currently in a crypotology class, and am working on building a RSA public key cryptology system for a class project. I am building the librarys just to get the experience to do so. However, I would ask if any of you know of any gaping security holes that can easily be seen from...
60
1950
by: rhle.freak | last post by:
Here is my code to generate prime numbers.It works absolutely fine when the range is *not very large*. However on initializing i with a large integer it produces erroneous results (some numbers ending in 5 ..which obviously cannot be prime numbers) can anyone please help me out with the reason?? /*Generate Prime Numbers*/ #include<stdio.h>
2
2613
by: QHorizon | last post by:
Hello, I'm new to Python (I've learned everything up to iterators so far) and fairly new to Programming. This would be my first real program: #Coordinate Geometry (The whole program is not shown) import math import sys print "Welcome to the Coordinate Geometry Calculator!"
0
9870
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9715
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
10940
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
1
10670
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
9451
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
7030
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
5882
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
4499
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
4087
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.