computing primes

As per my knowledge, I have seen the only following functions which will produce primes for $n$:

1. $n^2 - n + 41$

2. $n^2 + n + 41$

Of course both functions faile for $n = 41$ due to the polynomial representation. I tried to prepare a function which will generate primes continously. As we know that primes are infinite but there is a gaps between them and tough to produce all primes in a single function or algorithm. Please look my algorthm, which I belive that, it will produce only primes.

#include <iostream>

int testForPrime (int n) {
int p, i;
p = 1;
i = 3;
int result = n;
while (i < result) {
result = n / i;
if (n == i * result) {
p = 0;
i = n;
}
i = i + 2;
}
return (p);
}
int main (int argc, char * const argv[]) {
int p, i, n;
i = 3;
n = 5;
std::cout << "Initiating prime number generation sequence...\n\n1:2\n2: 3\n";
while (1) {
p = testForPrime (n);
if (p == 1) {
std::cout << i << ": " << n << "\n";
i++;
}
n = n + 2;
}
return 0;
}


For better undrestanding please see the my source file at by clicking EDIT of my post.

I would like to know the follwoing:

1. Is my algorithm is true or may be need more modifications?
2. If we restrict to number of primes less than x in terms of the zeros of the zeta function. The first term is $x/\log(x)$. The Riemann hypothesis is equivalent to the assertion that other terms are bounded by a constant times $\log(x)$ times the square root of $x$. The Riemann hypothesis asserts that all the 'non-obvious' zeros of the zeta function are complex numbers with real part $1/2$. how?

If you can give little more clarification on this second part, I will write another algorithm for justification of this second problem.

-
Please can you provide a checking table for your algorithm? – Hassan Muhammad Nov 29 '11 at 9:57
For $(2)$, a small correction, $\pi(x)=\frac{x}{\log x}+O(\sqrt{x}\log x)$ is provably false. Rather we have that $\pi(x)=\int_2^x \frac{1}{\log t}dt +O(\sqrt{x}\log x)\iff \text{RH is true}$. If by clarification, you are asking why this is true, it is related to Perrons formula and a contour integral of the zeta function. Specifically by integrating the logarithmic derivative of $\zeta(s)$ we can show that $$\sum_{p^k\leq x} \log p=x-\sum_{\rho:\ \zeta(\rho)=0} \frac{x^\rho}{\rho}+O(\log x)$$ and from here partial summation tells us about $\pi(x)$. – Eric Naslund Nov 29 '11 at 10:05
Your algorithm is an implementation of trial division and so it works. – Peter Phipps Nov 29 '11 at 12:30
As Listing points out you're not checking if a number is divisible by two. So your function thinks all powers of 2 are prime. This could be fixed by a simple special case at the beginning of your primality check. – JSchlather Nov 29 '11 at 12:47
@JacobSchlather That is true but the testforprime function is called only with odd values and so is correct in this context. – Peter Phipps Nov 29 '11 at 12:54

2 Answers

Your code, as Peter points out, is trial division and so it works. (The function testForPrime does not handle special cases like 1, powers of 2, or negative numbers but your code won't pass any of those to it.) This will correctly generate primes up to the limit of integers on your platform.

There are dozens, probably hundreds, of different algorithms that generate primes. Your code is of the generate-and-test variety and takes time $O(n^{3/2+o(1)}).$ Faster would be a sieve which would take time only $O(n^{1+o(1)}).$

The most efficient for all practical purposes are variants on the Sieve of Eratosthenes. The asymptotically fastest (but uncompetitively slow at all sizes at which it has been implemented) is the Atkin-Bernstein sieve.

-

I would suggest to use GMP's mpz_nextprime. Although it's based on a probabilistic primality test, IIRC it has been fully checked to work flawlessly within the limits of 32bit integers. Additionally I expect it to run faster than your code.

-