# 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

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)}).$