- --- Peter Boos <peter_boos@...> wrote:
>

<!--

> This might be an easy question, I think.

> Ehm I am thinking of writing a program, what should do

> sometihng with prime well the point is I wonder what

> is the optimum way of storing primes.

> I mean placing them in a file will require much space

> on HD. So I wondered then perhaps creating a single

> binary string of data in which a 1 represents a prime

> an a zero represent a non prime. wel that would allow

> me to place more primes in a file (although I am not

> sure as primes will ocure less with higher numbers.

> This binary prime file i will place it in a compressed

> folder. (a zip folder or an ntfs comressed folder)*.

>

> Wel my question is, what would be an better method for

> storing primes, then this binary way ?.

Liguististic aside, compare the etymology of

THAN (OE. _�anne_, _�onne_, _��nne_, also _�an_, _�on_; with

THEN (OE. _�anne_, _�onne_, _��nne_).

They used to be the same word, and may well return to that state!

-->

On the whole, no.

Some have looked into storing gaps between primes, but it's trivial to get a

bitmap representaton to out-perform (size-wise) such delta-coding, as long

as you permit yourself some special cases.

If you permit yourself to just 'know' that 2 is prime, then the bitmap

doesn't need to store all the unnecessary even numbers, which you know will

be all composite. => half size

If you permit yourself to also just 'know' that 3 is a prime, then the bitmap

no longer needs to contain numbers of the form 6n+3, as you know they're

divisible by 3. => 2/3rds of half size = 1/3.

If you also permit yourself to just 'know' that 5 is a prime, then the

bitmap no longer needs to contain numbers of the form 30n+5 and 30n+25, as

you know they're divisible by 5. => 4/5ths of 1/3 size = 4/15

Stopping here lets you store a bitmap range corresponding to 30 numbers in 8

bits, i.e. a byte.

Byte 0 contains bits corresponding to { 1, 7, 11, 13, 17, 19, 23, 29 }

Byte 1 contains bits corresponding to { 31, 37, 41, 43, 47, 49, 53, 59 }

...

Byte n contains bits corresponding to { 30n+1, 30n+7, ........ 30n+29 }

This is called using a "wheel". The wheel in this case has circumference 30

0------------------------------------->- Number line

29 1

######

##########

############ _

23 ############## 7 |\ roll

############## | this

############## / way

############

19 ########## 11

######

17 13

It's possible to use larger wheels,

2 -> 1 from 2

2.3 -> 2 from 6

2.3.5 -> 8 from 30

2.3.5.7 -> 48 from 210

2.3.5.7.11 -> 480 from 2310

Note, however, that it rarely makes sense to store tables of primes on

the hard disk, as in most computer languages it's almost always always

just as fast to calculate them on the fly. Hard disks are slow compared

to CPUs, on the whole.

> * As far as i now compression acka information

Information-theoretically, all the primes can be stored in only a couple of

> theorie this might be verry intresting question.

> Because it's how to store information of x primes with

> the less amount of storing data, so it would contain

> the essentials of primes... or something like that.

hundred bits, assuming that the primitives like division are atomic.

If you can describe the primes in a line of text, then that proves that the

information content is < 80*7 bits.

"Natural numbers with no proper divisors greater than 1" = 385 bits

"{p in|N:!Eq in|N,1<q<p:q|p}" = 196 bits

However, I've assumed that "|N" is known to mean "the natural numbers", and

":" means "such that", "!E" means "there does not exist" etc.

> Ohyeah

Thank you; and to you.

>

> A happy and peacefull newyear to all of you ! ! !

Phil

=====

I Pledge Allegiance to the flag

That appears on my Desktop Startup Screen.

And to the Monopoly for which it Stands:

One Operating System over all, inescapable,

With Freedom and Privacy for none. -- Telecommando on /.

__________________________________________________

Do you Yahoo!?

Yahoo! Mail Plus - Powerful. Affordable. Sign up now.

http://mailplus.yahoo.com - At 01:47 AM 12/30/2002 -0800, Peter Boos wrote:
>yep, right !

It should take very little time to generate the first 100,000 primes with a

>

>my hardware isn't that great it's a pentium 70.

>So when I want to do something with a lot of numbers

>this cost me lot's of time, for example checking the

>first 100.000 primes takes quite a while.

sieve of Erathostenes. Are you doing it a harder way?

>Now since i deal with this prime number file I just

I don't know what the absolute minimum space to store a list of primes is,

>wonder how to store them with the least amount of disk

>space.

but there will be a trade-off - the more compact the file, probably the

more processing it is going to take to get the numbers out.

If I'm going over 2^32 I generate them with a sieve. Less than 2^32 I

usually read them from a file. I have three types of file: the primes as

32-bit unsigned integers (the largest but easiest to deal with), the gaps

between successive primes, and a bit-vector. The last two take less space

and are good for various things, depending on what you need.

+---------------------------------------------------------+

| Jud McCranie |

| |

| Programming Achieved with Structure, Clarity, And Logic |

+---------------------------------------------------------+

[Non-text portions of this message have been removed]