Primality test and easy factorization

This is an algorithm that test if one number is prime and if the number it´s not prime returns the biggest factor of that number.

https://www.researchgate.net/publication/344177203_Primality_test_and_easy_factorization

Dear Mohamed Azzedine ,

The answer is yes. You can read our attached paper.

"On Formula to Compute Primes and the nth Prime"

m-hikari.com/ams/ams-2012/ams-73-76-2012/kaddouraAMS73-76-2012.pdf

It includes the required algorithm and a program to do the job as well.

Best regards

A 2. See also the same question posted 3 years ago

Answer 2 posted on January 14, 2019

See also the following question posted 3 years ago:

What is the fastest technique to find the next prime number

starting from a given prime P?

https://www.researchgate.net/post/What_is_the_fastest_technique_to_find_the_next_prime_number_starting_from_a_given_prime_P

With best regards, Jean-Claude

You can always do this using what some people call "brute force." You give me any number at all, either prime or not prime, even big number, and this algorithm will find the next prime greater than your number. Or by default, the algorithm begins with 3. (Well okay, it will reject even numbers. Just feed it any big odd number, doesn't need to be prime, if your want to start that way.)

Not only that, it will also point out all of the so-called "twin primes," as it is throwing out the endless series of prime numbers. Twin primes are two consecutive odd numbers, both of which happen to be prime, separated only by an even number (which is obviously not prime).

The attached code is written in QuickBasic, so it should be easy to follow. I have a small loop in there, to slow down the output initially, just so you can see individual primes as they are being generated. After this slower beginning, the thing takes off, spewing out primes faster than you can follow.

And the program allows one, optionally, to print the output to a text file, so you can study it later. Amazing thing is, those twin primes continue to exist, quite frequently, as long as I've ever run the program. (Eventually, you reach a limit of number size. As written, running in QB64, the numbers are dimensioned as 80-bit floating point, internally. So you can get to some very big values.)

Albert Manfredi

Thank you for your PrimeGenerator program. It works but it is limited to QB64 and time consuming with big numbers.

We are looking for a quick estimation with minimum operations (tests) < log N.

I would like to thank all followers for their answer.

I think no way, because the distribution of primes are not regular.

no, you also need the previous primes.

Then, you can do it:

Technical Report PRIME-GENERATING RECURRENCE: Development of a formula that c...

Test:

type following code in PariGP and you will see:

for(x=2,20,print(x," / ", prod(i=2,x-1,sin(Pi()*x/i),{i=1})))

Dear Chris De Corte

We don't need the previous primes.

For example, see the article

m-hikari.com › ams-2012 › ams-73-76-2012 › kaddouraAMS73-76-2012

Best regards

Dear Chris De Corte

We do not need the previous prime. I agree with Prof I.Kaddoura.

Dear Maged Z. Youssef

Prime number looks like not regular. They are regular and irregular in the same time.

Best regards

You can use a prime sieve algorithm in the interval (100003, 100020)

Marouane Rhafli

Your answer to what?

Issam Kaddoura We can use a segmented prime sieve to generate the next prime,

Marouane Rhafli

This method used to search for primes less than sqrt(n).

And not for the next prime.

the segmented prime sieve searches for primes up to N by using primes up to sqrt(N).

Somehow you can sieve on small interval to generate only 2 primes

Issam Kaddoura by the way i'm reading your file http://m-hikari.com/ams/ams-2012/ams-73-76-2012/kaddouraAMS73-76-2012.pdf

It seems interesting for me as i'm developing a new prime counting function and a new primality test

Marouane Rhafli

This is another task. Our problem is:

If P is an arbitrary prime, what is the next prime?

Issam Kaddoura i already gave my suggestion to compute the next prime

Marouane Rhafli

All possible new results and all potential improvements are welcome.

Dear Mohamed Azzedine, this is not true.

Suppose someone gives you a very high prime number n then you can only guess the position of the next prime using the formula provided by Riemann or mine:

Technical Report Better approximation for prime counting function than π(x)

To know exactly where the next prime will be, you need to know all the previous primes and do a calculation as follows:

Technical Report PRIME-GENERATING RECURRENCE: Development of a formula that c...

Dear Chris De Corte

I would like to suggest a pattern to get the next prime after a given prime.

First compute the integer Q=sqrt (N) then compute R=Q(Q+1).

Compare the result to N. The difference D is positive (nearrest to N) then compute E= (Q-1)Q ,

the difference F with N is negative (nearrest to N).

The next prime after N could be Q(Q+1)-D or (Q-1)Q+F. If you do not get a prime number then decrease D or increase F. After (logN)/2 tests you will reach the next prime. Choose carefully the new values for D and F in order to avoid even number.

For a prime p=100003

sqrt(100003)= 316 , R=316 x 317=100172 , D=+169 and

E=315 x 316=99540 ,F= - 463

D={165,163,161,159,157,153}

F={467,469,471,473,477,479}

Number of test is 6=(logN)/2

next prime=99540 + 479=100019

or

next prime=100172 - 153=100019

Best regards

Dear Mohamed Azzedine

Frankly, your computations are not clear.

You said:

Q(Q+1) - D = Q2 + Q - D = N + sqrt(N) - D

Q(Q-1)+F = Q2 - Q + F = N - sqrt(N) +F

what is the significance of such values?

What are the bounds of D and F?

D < Q !! and F > Q !! are necessary conditions.

What are you trying to say?

Best regards

A-21 Positive integers that are the most allergic to squares

Answer 21, posted on October 2, 2019.

--------------------------------------------

Concerning the integers Q(Q + 1) considered by Mohamed

in answer 19, we may think that they are very close

from the square Q^2 = QQ, because (Q + 1) is just one unit

away from Q.

The opposite is true:

When Q is a positive integer, the integer Q(Q + 1) is

as far away from a square as possible:

It is almost, up to ½, in the middle

between QQ and (Q + 1)(Q + 1).

For example, (4)(5) = 20 is ½ below 20.5,

which is the middle of the interval [16, 25]:

(4)(4) < (4)(5) < (5)(5),

16 < 20 < 25.

https://en.wikipedia.org/wiki/Pronic_number#As_figurate_numbers

These numbers are called “Pronic numbers”:

https://en.wikipedia.org/wiki/Pronic_number

--------------------------------------------

With best regards, Jean-Claude

Dear Issam Kaddoura

Your comment is not a mathematical question nor an a mathematical answer.

The suggested method is clear, pratice and precise. It is followed by an example.

It gives an estimation of the next prime and it allows to compute it in a limited number of test. The number of test is t=lob (N)/2.

This method is more quick than the cassical sieve .

It is obvious that D < Q and F>Q.

You can try it for any given prime. It works .

Best regards

M.Azzedine

Dear Mohamed Azzedine

In my previous comment, I asked you to explain your calculations.

The only conclusion in your comments is that:

(the next Prime is greater than the previous one).

You need to show exact precise bounds for the next prime.

For example, the following statements are clear.

(1) The next prime to p is less than 2p. ( Bertrand postulate).

(2) nlog(n) + nlog(logn) - 2n < Pn < nlog(n) + nlog(logn)

for 6 < n < exp(95) B.Rosser. Pn is the nth prime.

Or similar clear statements, etc.

Best regards

A-24 A popular simple big improvement of Bertrand’s postulate

Answer 24, posted on October 6, 2019.

--------------------------------------------

Bertrand’s postulate, is the proved theorem

that says that for any integer n > 3, there exists

at least one prime p such that n < p < 2n – 2.

https://en.wikipedia.org/wiki/Bertrand%27s_postulate#Better_results

Bertrand’s postulate was first conjectured in 1845

by Joseph Louis François Bertrand (1822–1900).

https://en.wikipedia.org/wiki/Joseph_Bertrand

It was completely proved by Pafnuty Lvovich Chebyshev (1821–1894)

in 1852.

https://en.wikipedia.org/wiki/Pafnuty_Chebyshev

--------------------------------------------

A first big very simple and very easy to remember

big improvement is the following:

For every integer n such that n > 24,

there exists at least one prime p

such that n < p < (1.2)n.

This was proved by Jitsuro Nagura in 1952.

https://en.wikipedia.org/wiki/Bertrand%27s_postulate#Better_results

--------------------------------------------

With best regards, Jean-Claude

Primality test and easy factorization

This is an algorithm that test if one number is prime and if the number it´s not prime returns the biggest factor of that number.

https://www.researchgate.net/publication/344177203_Primality_test_and_easy_factorization

Formula to find the next prime number with Fibonacci index

Prime numbers follow a pattern of the form of a Fibonacci sequence.

https://www.researchgate.net/publication/348635030_Formula_to_find_the_next_prime_number_with_Fibonacci_index