# Questions tagged [primes]

The tag has no usage guidance.

118 questions
Filter by
Sorted by
Tagged with
56 views

### What is the time complexity of this algorithm of finding all prime numbers?

I came up with this algorithm for finding all prime numbers from 1 to n. This algorithm could already exist, if it does I don't know what it is called. ...
59 views

### How to allocate memory for prime numbers

I was working on an algorithm to find prime numbers, and I needed to allocate memory for each prime number that I found so far. I will do a search up to N and need to allocate all memory in advance. I ...
115 views

### A new algorithm for determining if a number is prime or not

This approach has been on my mind for quite some time. I did come up with it myself, I searched some methods for determining prime numbers but never came across anything similar to this. ...
43 views

### Universal hash functions and prime number modulus scheme

Definition of a universal hashing function $h: U \rightarrow[m]$ (where $[m]=\{0, \ldots, m-1\}$) is that for any given distinct keys $x,y \in U$, when $h$ is picked at random (independently of $x$ ...
1 vote
39 views

### Is Miller-Rabin not a suitable algortihm for the RSA key generation or am I missing something?

I'm trying to recreate the RSA key generator, from what I understood you must create two prime numbers of 256 bytes long, p and q...
37 views

### Minimum even goldbach partitioning

The following is an excerpt taken from Oliveria's paper "Empirical verification of the even goldbach conjecture...", it gives an alternative segmentable minimal interval partitioner for the ...
118 views

...
82 views

55 views

### Solve SUBSET SUM for Reciprocals of Primes

Let $p_1, ..., p_n$ distinct prime numbers with $P = \prod_{i=1}^{n}{p_i}$ and $A=(a_1, ..., a_n)$ with $a_i = P/p_i$. Problem Show the SUBSET SUM problem $(A, \alpha)$ can be solved in polynomial (...
471 views

### Time complexity of Sieve of Eratosthenes [closed]

Wikipedia states that the Sieve of Eratosthenes runs in time $O(n\log\log n)$. Why is that so?
1 vote
89 views

### Is binomial(n, k)=0 (mod n) when gcd(n, k)=1? When gcd(n, k)>1?

I was programming the AKS primality test, and I have two questions. Is it correct that if gcd(n, k)=1, then binomial(n, k)=0 (mod n)? Is it correct that if gcd(n, k)>1, then binomial(n, k)>0 (mod n)?...
160 views

### Is the Time Complexity of Trial Division Exponential? [duplicate]

I know that there is already a similar question asked on here, but after reading the wiki page on trial division, I am confused, and the other answer doesn't help. The wiki page states that when doing ...
1 vote