# Questions tagged [primes]

The tag has no usage guidance.

85 questions
Filter by
Sorted by
Tagged with
566 views

### Efficiently computing the smallest integer with n divisors

In order to tackle this problem I first observed that $$\phi(p_1^{e_1} \space p_2^{e_2} \cdots \space p_k^{e_k}) = (e_1 + 1)(e_2 + 1)\cdots(e_k +1)$$ Where $\phi(m)$ is the number of (not ...
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 ...
130 views

### Modifications to speed up the AKS primality proving

It is clear that AKS primality proving is the newest one, but as the results show it is not the fastest one. When I try the 9 digits long prime number it consume about 6 minutes to give you the ...
174 views

### Average runtime of naive primality test

The naive prime test goes something like this: is_prime(n): for(i=2; i<=sqrt(n); ++i): if n mod i == 0 : return false return true If $n$ is ...
344 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 ...
Given an input $m$, I am trying to find an algorithm that will give me the number $p$ that is closest to $\tfrac47 m$ and co-prime with $m$. Where $m$ is odd, I have no problem producing an outcome ...