1
$\begingroup$

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   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.

  • 0
    Please can you provide a checking table for your algorithm?2011-11-29
  • 3
    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)$.2011-11-29
  • 0
    Your program is obviously wrong too, $\text{testForPrime}(8)=1$ but $8=2^3$ is no prime.2011-11-29
  • 4
    Your algorithm is an implementation of [trial division](http://en.wikipedia.org/wiki/Trial_division) and so it works.2011-11-29
  • 1
    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.2011-11-29
  • 1
    @JacobSchlather That is true but the testforprime function is called only with odd values and so is correct in this context.2011-11-29
  • 0
    @Peter, ah so it is.2011-11-29

2 Answers 2