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 20031120, 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!
On Mon, 17 Nov 2003 11:46:08 0600, James Hu <jx*@despammed. com>
wrote: On 20031117, Christopher BensonManica <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, strengthreduce vsquared in the loop by adding 2*v1
for each increment, or 2*(v1)+2*v2 aka 4*v4 for incrementby2.
 David.Thompson1 at worldnet.att.ne t
On 20031122, 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
In <3F************ ***@yahoo.com> CBFalconer <cb********@yah oo.com> writes: Eric Sosman wrote: James Hu wrote: > On 20031120, 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
Dan Pop wrote: In <3F************ ***@yahoo.com> CBFalconer <cb********@yah oo.com> writes:
Eric Sosman wrote: James Hu wrote: > On 20031120, 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!
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
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!
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
On Sat, 22 Nov 2003 00:11:22 0600, James Hu <jx*@despammed. com>
wrote: On 20031122, 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 previouspost 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 compiletime 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
On 20031127, Dave Thompson <da************ *@worldnet.att. net> wrote: On Sat, 22 Nov 2003 00:11:22 0600, James Hu <jx*@despammed. com> wrote: On 20031122, 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 previouspost 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 compiletime 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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics 
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^610^8 range
so it would have to fairly efficient
Dag

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...

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

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.

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....
 
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

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...

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>

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!"

by: marktang 
last post by:
ONU (Optical Network Unit) is one of the key components for providing highspeed 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...

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,...
 
by: Oralloy 
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bitfields 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...

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,...

by: agi2029 
last post by:
Let's talk about the concept of autonomous AI software engineers and nocode 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...

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();...

by: adsilva 
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?

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
 
by: muto222 
last post by:
How can i add a mobile payment intergratation into php mysql website.
 