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
    @Peter, ah so it is.2011-11-29

2 Answers 2

5

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.

3

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.