1
vote
1answer
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
2answers
725 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
1answer
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
3answers
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
2answers
763 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
5answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
3answers
912 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
2answers
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
2answers
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
2answers
924 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
9answers
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
4answers
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. ...