# Questions tagged [primes]

The tag has no usage guidance.

8 questions
Filter by
Sorted by
Tagged with
195 views

### Primality testing: Why is dividing a number $n$ by every integer between 2 and $\sqrt{n}$ an inefficient test?

In the paper "PRIMES is in P" the following is said (page 1): Let PRIMES denote the set of all prime numbers. The definition of prime numbers already gives a way of determining if a number $n$ is ...
41k views

### Why is it best to use a prime number as a mod in a hashing function?

If I have a list of key values from 1 to 100 and I want to organize them in an array of 11 buckets, I've been taught to form a mod function $$H = k \bmod \ 11$$ Now all the values will be placed ...
6k views

### Data compression using prime numbers

I have recently stumbled upon the following interesting article which claims to efficiently compress random data sets by always more than 50%, regardless of the type and format of the data. Basically ...
154 views

### How to compute all primes between upto $n$ in time $O(n)$ time?

Suppose that I want to compute all the prime numbers between 2 and $n$. The natural way or most obvious way to do so is given below. Let $A$ is an array contain the numbers from $1$ to $n$. For $j=2$ ...
996 views

### Is determining if there is a prime in an interval known to be in P or NP-complete?

I saw from this post on stackoverflow that there are some relatively fast algorithms for sieving an interval of numbers to see if there is a prime in that interval. However, does this mean that the ...
85 views

### Assign unique integer keys to sets

I am given a list of $n>1$ arrays, where each array has fairly small number of elements (rarely above $5$). Also $n$ is quite small in practice (around $6$). My problem is that I would like to ...
Let UID denote a unique identifier. UID's are represented as 6-digit positive integers. I want to insert a collection of UID's in a hash table with $M$ buckets, where $M$ is a prime number (for ...