Prime number algorithm in C

C

CBFalconer

Eric said:
James said:
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.
 
D

Dave Thompson

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(unsigned 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.net
 
D

Dan Pop

In said:
Eric said:
James said:
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
 
C

CBFalconer

Dan said:
In said:
Eric said:
James Hu 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
:)
 
D

Dan Pop

In said:
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
 
C

CBFalconer

Dan said:
.... snip ...

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 :)
 
D

Dave Thompson

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_max,
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.net
 
J

James Hu

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_max,
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
 
E

Eric Sosman

James said:
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.

If you're using the `%' operator to check a candidate
for divisibility, there's an excellent chance that the
`/' to check for end-of-range is "free."

for (div = 3; number / div >= div; div += 2)
if (number % div == 0)
...

Many compilers will perform just one division to generate
both the quotient and the remainder.
 
B

Ben Pfaff

Eric Sosman said:
If you're using the `%' operator to check a candidate
for divisibility, there's an excellent chance that the
`/' to check for end-of-range is "free."

for (div = 3; number / div >= div; div += 2)
if (number % div == 0)
...

Many compilers will perform just one division to generate
both the quotient and the remainder.

In case it isn't smart enough, you can encourage it by using the
standard C library div() function.
 
Joined
Jul 22, 2009
Messages
1
Reaction score
0
Prime number algorithm in C++

#include <iostream>
using namespace std;

void findPrime(int n)
{

int i,j;
int nn = n+1;
bool array[nn];
array[0] = false;
array[1] = false;
for (i=2; i<nn; i++)
{
array = true;
}
for(i=2; i<nn; i++)
{

for (j=2; (i*j)<nn; j++)
{
array[i*j] = false;
}
}

for(i=0; i<nn; i++)
{
if(array)
{
cout<<i<<" is prime";
cout<<endl;
}
}

}

int main()
{

int n = 100;
findPrime(n);

}

works for me!
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Function for primes 0
Java 1
Complex Python challenge 1 3
Q for a source code in an exercise 1
Function is not worked in C 2
Langton's Ant 0
Prime number generator 11
C Programming functions 2

Members online

Forum statistics

Threads
473,744
Messages
2,569,479
Members
44,900
Latest member
Nell636132

Latest Threads

Top