• ### What is your GameDev Story?

#### Archived

This topic is now archived and is closed to further replies.

# Primes

This topic is 5823 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

this is a pre-emptive *not* homework statement. Suppose I have a list of the first N primes of which the last one is P Let Q by the product of all these primes plus one: Q = 2*3*5*7...*P + 1 the result must be prime since it has no prime factors, division by any smaller prime will have a remainder of one are there any prime numbers between P and Q? ******** A Problem Worthy of Attack Proves It''s Worth by Fighting Back

##### Share on other sites
N=2
P=3

Q=2*3 + 1 = 7
between P=3 and Q=7 there is 5

##### Share on other sites
There has to be because of some theorem that I think is called Bertrand's Posulate, saying that for all P prime, there exists a prime between P and 2P. The proof of this is very complex, and I think Erdos has one of the simplest proofs that he came up with when he was in his late teens. Since P in your expression is multipled by every prime before that, and every other prime is greater than 2, I think that by this theorem there are at least N primes, where N is the number of primes up to P, between Q and P.

Brendan

[edited by - Punty50 on February 7, 2003 12:00:14 PM]

##### Share on other sites
quote:
Original post by walkingcarcass
Let Q by the product of all these primes plus one: Q = 2*3*5*7...*P + 1
the result must be prime since it has no prime factors, division by any smaller prime will have a remainder of one

Err... Nope.

2*3*5*7*11*13 + 1 = 30031 = 59*509

##### Share on other sites
I''m not sure where you got this setup from, but it reminds me of the proof that there are infinitely many primes... it states that if there are a finite number, then multiply them together, and add 1. Then, that must be prime, which means that there is another prime outside of the previously defined set of ALL of them, reduxio ad absurdum. But that one only works if you have ALL the primes, because every natural number can be broken down into one and only one list of primes (viz. Fundamental Theorem of Arithmetic), and therefore if it couldn''t be divided my anything in the original list (all primes), it couldn''t be a natural number, but all the closure in supposition says it would be.

Anyhow, that''s why alvaro could find a counterexample, because your lis lacks the properties I stated above. These things make a lot more sense in my head, I might come back and explain it in simpler terms later, but I wouldn''t count on it ;-).

##### Share on other sites
Yeah, it doesn''t work all the time.
But the reason it works a lot of the time is because
whenever you have a list of primes p1...pn and
a number r that is relatively prime to all these numbers,
(the product of primes(p1...pn))+r can be prime.
In fact, all primes can be expressed in this way. I developed
a prime-number-finding algorithm based on this discovery.
The running time of my algorithm is O(n/log(log(n))).
That''s sub-linear! So in theory, you could find all the primes
up to n in less than n steps. The running time assumes
operations such as multiplication and division in unit time,
regardless of the size of the numbers. The trick in the algorithm
is how I eliminate the composite numbers generated by the
formula above. The bad part of the algorithm is that it requires
O(n/log(log(n))) memory (where a unit of memory can hold
an arbitrarily large number no greater than n). So I''ve
only been able to generate all primes up to about 300,000,000.
After that, I run out of memory.

Steven Borkman
Video Game Page: http://www.dev.mygamesite.net

##### Share on other sites
quote:
2*3*5*7*11*13 + 1 = 30031 = 59*509

the prrof says that the result must either be a prime number OR can be divided by a new prime number that was not in the original list of prime numbers used.

##### Share on other sites
quote:
Original post by alvaro
[quote]Original post by walkingcarcass
Let Q by the product of all these primes plus one: Q = 2*3*5*7...*P + 1
the result must be prime since it has no prime factors, division by any smaller prime will have a remainder of one

Err... Nope.

2*3*5*7*11*13 + 1 = 30031 = 59*509

That''s because the actual theorem is: either the result is prime or it is a multiple of a prime larger than P. In this case it is a multiple of 59, a prime larger than 13.

8 billion HTTP 500 errors....

##### Share on other sites
Yeah, same thing, it''s outside the set, and it''s larger, you''re both right, it''s just always larger in this case because we''re starting at zero and not skipping any.

About that algorithm though... very interesting, you know there''s a contest on to find ridiculously large primes, if you can get one with I think 1 million decimal digits, they''ll award you 100 grand. Might be worth the investment if you KNOW you could do it with more memory.

##### Share on other sites
Is there actually an algorithm to definitively prove you have a prime (other than just trying every possiblility upto the number in question)...I understood that there are no perfect algorithms for this

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 10
• 11
• 13
• 9
• 11
• ### Forum Statistics

• Total Topics
634089
• Total Posts
3015460
×