473,499 Members | 1,738 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Next prime algorithm

Does anyone know 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
Nov 14 '05 #1
6 8952
In article <2j************@uni-berlin.de>, ckroom <ck****@hotmail.com>
wrote:
Does anyone know a good algorithm to get the next prime of a number n?

prime = nextprime( n );

It's for some stuff about double rehashing, thanks.


Try if n+1 is a prime number. If it isn't then try n+2. And so on. And
so on. You know how to find out if a number is a prime, don't you?
Nov 14 '05 #2

"ckroom" <ck****@hotmail.com> wrote
Does anyone know a good algorithm to get the next prime of a
number n?

prime = nextprime( n );

It's for some stuff about double rehashing, thanks.

Just because you are implementing your algorithm in C doesn't make it
topical here.

However you can first sieve the list for factors of small prime numbers,
then do many tests for primality using the "witness" method, but finally to
be 100% sure you need to do an exhaustive search up to the square root of
the number you are testing.
Nov 14 '05 #3
Hi there,

Does anyone know a good algorithm to get the next prime of a number n?

prime = nextprime( n );

It's for some stuff about double rehashing, thanks.


Not really on topic.
Apart from the other answers you got, there is yet another way.

If the maximum argument to nextprime is limited by a small enough
number, you can calculate all primes up to the successor of that maximum
argument, using e.g. the Sieve of Eratosthenes, and store them in
an efficient manner, say set bits, exclude multiples of small prime
numbers. Then, essentially, you only have to search in your list for the
next set bit. Some time ago, I came across

http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html

However, I only had a look at the explanations, not at the source.
The author assumes 8 bits per byte which may not be true on your
machine - nonetheless, the idea is nice enough.

BTW: If the maximum is too high, just write all the required primes
to a file and read them into an array (->density of primes within
natural numbers; use the theory to predict the position of n and
search for n from that position in your array).
HTH
Michael

Nov 14 '05 #4
In article <ca**********@newsg3.svr.pol.co.uk> "Malcolm" <ma*****@55bank.freeserve.co.uk> writes:
"ckroom" <ck****@hotmail.com> wrote
Does anyone know a good algorithm to get the next prime of a
number n?
.... Just because you are implementing your algorithm in C doesn't make it
topical here.

However you can first sieve the list for factors of small prime numbers,
then do many tests for primality using the "witness" method, but finally to
be 100% sure you need to do an exhaustive search up to the square root of
the number you are testing.


Wrong. But the reasons are very off-topic here. (Primality proving programs
have in general a running time much better than O(sqrt(n)).)
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Nov 14 '05 #5
ckroom wrote:

Does anyone know a good algorithm to get the next prime of a
number n?

prime = nextprime( n );

It's for some stuff about double rehashing, thanks.


You can look in the source to hashlib for one method. See my site
below, download section.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 14 '05 #6
On Sun, 13 Jun 2004 20:11:39 +0200, ckroom <ck****@hotmail.com> wrote:
Does anyone know a good algorithm to get the next prime of a number n?

prime = nextprime( n );

It's for some stuff about double rehashing, thanks.


In spite of all the answers you've got, I think your question is
ambiguous. What do you mean by "the next prime of a number n"? Do you
mean the smallest prime greater than n? Do you mean the next prime
factor of n?

In any case, it's off-topic here.

--
Al Balmer
Balmer Consulting
re************************@att.net
Nov 14 '05 #7

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

Similar topics

36
8347
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,...
9
2682
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...
5
2707
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...
11
7124
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...
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
32
76370
by: Cmorriskuerten | last post by:
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...
20
6784
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...
25
3847
by: johnmsimon | last post by:
i need to develop a code that finds a prime right number between 2 and 100000. and print one line of text that indicates if the int. is right prime. i am in beginning programing so complex is...
2
2576
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...
12
6183
by: electric916 | last post by:
I have a homework assignment i Am totally confused on. I started with a basic code to determine if a number is prime or not, but need guidance from here. I will post assignment details then what I...
0
7006
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...
0
7169
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,...
0
7385
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
0
5467
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,...
1
4917
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new...
0
3088
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
0
1425
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 ...
1
661
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
0
294
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence...

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.