Dear Issam Kaddoura and Yasser Jaamour

Thanks, I appreciate all that you have provided, we understand that we must be careful in choosing the appropriate title for our article.

It was noticed in https://en.wikipedia.org/wiki/Formula_for_primes that “In number theory, a formula for primes is a formula generating the prime numbers, exactly and without exception. No such formula which is efficiently computable is known. A number of constraints are known, showing what such a "formula" can and cannot be”. Related twelve references are also available at https://en.wikipedia.org/wiki/Formula_for_primes.

Useful links concerning the proposed question, by Eric W. Weisstein, are also available at http://mathworld.wolfram.com/PrimeFormulas.html and http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html.

Dear Adiya K. Hussein ,

To find a formula that generates prime numbers is different than a method to count prime numbers. There are many formulas proposed to test the primality of a given number. That is, for a given n; some algorithms can test if n is a prime number or not. Many tests are available, for example: (1) if ((n-1)! +1)/n is an integer, then n is prime if not, then n is composite. (Wilson's) This test is not efficient to test the primality of n; it depends on n!. (2) Find all primes less than sqrt(n), if n is not divisible by any prime less or equal sqrt(n), then n is prime. There are thousands of algorithms to test primes. Lately ( 2004 ) some authors proved that [primes is in P, see the paper] , that is n can be tested with an algorithm that has a polynomial of time complexity. In the presence of primality test, one can use the algorithm to construct a prime number. But the main problem: what is the complexity of this algorithm? (The time needed to construct this prime)  I have constructed a formula for the nth prime (see my paper) P_n, this formula is computable for small n, we know that for example, p_(2^100000000000) is a prime. But the formula may run, using advanced programs, thousands of years to show the digits of this number. So this formula is not efficient for large numbers n. Mathematicians challenge is to discover an efficient explicit computable formula f(n) that provides prime numbers with a deterministic period. On the other hand, some formulas compute the number of primes within a given interval without pointing them. For example: If p1, p2....,pn are the prime numbers less than √N,then

π(N)=[N]+ n-1- ∑i [N/pi] +∑i

Dear Romeo Meštrović and Issam Kaddoura

Thanks. I appreciate all the clarifications you have given , we can say that there is no formula till now to generate prime numbers , thus the most existing formulas are to distinguish the number if it is prime or composite . So it is neither generating nor computing formulas.

As the main methodology to FIND a prime is to generate numbers and test for primality, then the term generate is closer than compute.

An interesting fast method for primlity test is that based on Montgomery test, with some limitations that must be considered.

Dear Adiyah,

There are efficient methods to count the exact number of primes below any number N. The approximation of this number is N/logN .

In my previous answer, I show a known formula:

π(N)=[N]+ n-1- ∑i [N/pi] +∑i

Dear Yasser,

I think you want to turn attention to the following paper:

P. Montgomery, Modular Multiplication without Trial Division, Math. of Computation, vol. 44, pp. 519-521, 1985.

Indeed it is useful in modular arithmetic.

Best regards

Dear Issam Kaddoura and Yasser Jaamour

Thanks, I appreciate all that you have provided, we understand that we must be careful in choosing the appropriate title for our article.

If the formula is to find prime numbers, it is preferable to say (formula to generate prime numbers) and if it is to find number of prime numbers precedes a certain number then we say( formula to compute ...)

I agree with the clarifications of Issam Kaddoura that to find a formula that generates prime numbers is different than a method to count prime numbers.

Dear Peter Breuer ,

Here we are talking about exact values where relations are defined over discrete domains. It is weird to introduce the notation of derivative in such formulas. You may do that in the general definition where answers are supposed to be approximations and not exact.

Approximations are work to estimate the number of primes below N as N/log(N),

but how we can use derivatives at a given number to decide whether it is prime or not. I agree that one can use the pi formula to test primes as: For n is odd, if pi(n) - pi(n-1) = 0 , then n -1 is composite and if pi(n) - pi(n-1) = 1, then n-1 is prime. Conversely, if T is a formula to test primality of n, then we construct a delta function such that delta(T(n)) =1 if n is prime and 0 otherwise.

Taking the sum overall the numbers below N, we obtain pi(N).

Best regards

Dear colleagues,

The question proposed by Adiya K. Hussein is unfortunately up to now an unsolved problem. Furthermore, related earlier investigations suggsest that it is very difficult problem in Number Theory.

Best regards,

Prof. Dr. Romeo Meštrović

Dear Peter Breuer ,

In this case,

D(pi(n))= pi(n) - pi(n-1) all your conclusions and results are correct.

Best regards

Dear colleagues, The discussions that you have presented are really very useful. We appreciate all that you have provided.

نعم يوجد فرق بينهما