# Tagged Questions

**1**

vote

**1**answer

79 views

### computing $c_5$ in “Primality testing with Gaussian periods”

As far as I know, the April 2011 version of #143 on this page has not been improved upon.
On page 10 of that paper, the authors give an algorithm that uses a constant $\:c_{\hspace{.01 in}5}\:$.
...

**6**

votes

**2**answers

726 views

### Approximate number of primes below a given integer?

The problem of the complexity of the exact counting problem for primes is interesting. The best result we have about primes is that it is hard for TC0. But counting the number of witnesses to a TC0 ...

**2**

votes

**1**answer

320 views

### At what point does Miller-Rabin become faster than trial division?

I've read in various places (and know) that Miller-Rabin is a much faster primality test than trial division for large $N$, but is much slower than trial division for small $N$.
My question is: how ...

**2**

votes

**3**answers

2k views

### Algorithm for detecting prime powers

While reading Peter Shor's paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, I came across the following quote:
"This scheme will thus work as ...

**1**

vote

**2**answers

764 views

### The relationship between the Dirichlet Hyperbola Method, the prime counting function, and Mertens function

I have a question concerning the connection between the Dirichlet Hyperbola Method and properties of both the Mertens function and the prime counting function.
Preliminary: Mertens function and the ...

**16**

votes

**5**answers

3k views

### Fastest Algorithm to Compute the Sum of Primes?

Can anyone help me with references to the current fastest algorithms for counting the exact sum of primes less than some number n? I'm specifically curious about the best case running times, of ...

**-1**

votes

**1**answer

660 views

### The “universal” diophantine equation

There is a diophantine equation in some number (I think the minimum is now 9) of variables, that can be used to represent
All other diophantine equations (could be wrong on this)
Any particular set ...

**2**

votes

**0**answers

288 views

### Algorithm for keeping a concrete version of Euclid's argument simple

(A version of this same question was posted to stackexchange.)
Suppose we do what Euclid wrote about: starting with a finite set of primes, multiply them, add or subtract 1, factor the result, append ...

**3**

votes

**1**answer

395 views

### Find the least prime $p$ such that $mn$ divides $p-1$

My hope is that this question is "trivial," but it is outside my knowledge base, so I'd appreciate some advice.
Given positive integers $m$ and $n$, find the least prime $p$ such that $p-1 = mnk$ ...

**2**

votes

**0**answers

329 views

### Prime generating algorithm

If I want an algorithm that outputs any $n$ distinct prime numbers, is there anything faster than Atkins' Sieve $O(n/log(log(n))$ ?

**4**

votes

**1**answer

344 views

### Can we count primes in residue classes quickly?

Using combinatorial methods (due to Legendre, Lehmer, Meissel, Lagarias, Miller, Odlyzko, Deléglise, Rivat, and probably others) it's possible to count the number of primes up to $N$ quickly -- in ...

**6**

votes

**3**answers

914 views

### Prime counting - any fast alternatives to the Lagarias-Miller-Odlyzko combinatorial method or the Lagarias-Odlyzko analytical methods?

I guess the question says it all - I'm trying to track down fast algorithms for prime counting to know what's out there.
I'm already familiar with the two algorithms mentioned in the title ...

**6**

votes

**2**answers

1k views

### Can a number be factored quickly, given the sum of its prime factors?

This is perhaps most naturally phrased as a promise problem. Given numbers $n$ and $s$, where $s$ is the sum of the prime factors of $n$ (distinct or with multiplicity; I imagine both variants will ...

**13**

votes

**2**answers

995 views

### Detecting almost-primes quickly

There are many fast algorithms (deterministic and probabilistic) for detecting primality. Are there any fast algorithms (probabilistic ones allowed) known for detecting whether a number is the product ...

**8**

votes

**2**answers

925 views

### Computing the Mertens function

I wonder if anybody can help me with this problem.
I'm trying to compute the Mertens function for large $n$. The most obvious algorithm is just to compute all primes up to $\sqrt{n}$ and then to ...

**6**

votes

**9**answers

2k views

### Marey's problem: Generating all prime numbers in $[n_1,n_2]$

Is there are some references to algorithms that generate the set of prime numbers located between two given numbers n1 and n2?
I would like to consider the cases when n1 is large while n2-n1 is small ...

**33**

votes

**4**answers

7k views

### How hard is it to compute the number of prime factors of a given integer?

I asked a related question on this mathoverflow thread. That question was promptly answered. This is a natural followup question to that one, which I decided to repost since that question is answered.
...