A way to store primes in python (i.e. have a list that checks if a element is there, and that can output elements in order)

Question

I want to store a list of primes, in a way that both allows me to iterate over it (in order) and to check quickly if a given prime is there.

What is the best way ?

Should I just use a list? In this case, I suppose that there is a builtin for binary search. What is it ?

Should I use both a list and a set ? I know this works from the point of view of efficiency, but I'd like a way that is a bit less messy ...

Is it relevant that they are primes, or is that only incidental? And if it is relevant, is there a reason not to just have an infinite primes detector? — Silas Ray, Aug 24 '12 at 23:19
Sounds like you're looking for an ordered set See http://stackoverflow.com/questions/1653970/does-python-have-an-ordered-set#1653974 — dfb, Aug 24 '12 at 23:19
Although, for a finite set of (sorted) numbers, a binary-search over a simple list may also have desirable/sufficient characteristics .. — , Aug 24 '12 at 23:21
@sr2222 : not incidental. I am dealing with this right now. I am not sure what you mean, though. A function that tests for primality ? — josinalvo, Aug 24 '12 at 23:25

JBernardo · Answer 1 · 2012-08-24T23:41:29.827

0

If ordered sets sound overkill for doubling the storage, you can keep the list and use the bisect module for O(log n) lookups. It does binary search on sorted lists.

edited Aug 24 '12 at 23:41

answered Aug 24 '12 at 23:35

JBernardo

32,262
10
90
115

A way to store primes in python (i.e. have a list that checks if a element is there, and that can output elements in order)

1 Answers1