Questions tagged [primes]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
2answers
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 ...
52
votes
4answers
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 ...
21
votes
5answers
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 ...
4
votes
1answer
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$ ...
13
votes
1answer
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 ...
4
votes
2answers
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 ...
3
votes
3answers
311 views

What is the fastest to find just smallest prime number to a given number N where N can be as large as 10^18?

During a programming contest I was asked to find just smallest prime number to given number N. As Sieve cannot be used and brute force also doesn't work. So, I was wondering is there any other faster ...
2
votes
3answers
2k views

Hash function to hash 6-digit positive integers

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 ...