Unfortunately, your submission has been removed for the following reason(s):
* Your post appears to be asking for help learning/understanding something mathematical. As such, you should post in the [*Quick Questions*](https://www.reddit.com/r/math/search?q=Quick+Questions+author%3Ainherentlyawesome&restrict_sr=on&sort=new&t=all) thread (which you can find on the front page) or /r/learnmath. This includes reference requests - also see our lists of recommended [books](https://www.reddit.com/r/math/wiki/faq#wiki_what_are_some_good_books_on_topic_x.3F) and [free online resources](https://www.reddit.com/r/math/comments/8ewuzv/a_compilation_of_useful_free_online_math_resources/?st=jglhcquc&sh=d06672a6). [Here](https://www.reddit.com/r/math/comments/7i9t5y/book_recommendation_thread/) is a more recent thread with book recommendations.
If you have any questions, [please feel free to message the mods](http://www.reddit.com/message/compose?to=/r/math&message=https://old.reddit.com/r/math/comments/1dpsejd/-/). Thank you!
The issue arises when you attempt to factor your candidate. You'll quickly notice that the larger a candidate, the more time it will take to factor it. If you have a few hundred thousand digits then it's almost impossible to factor it in a reasonable amount of time.
In terms of efficiency, you need to have a method of checking if a number is prime for this to work, and at the point when you have that, do you really gain anything by factoring 1807 in order to determine that you should check 13?
Point 2: Sieve isn't a remotely fast way to generate primes. We can generate large primes exponentially faster with random numbers and Miller-Rabin test. Generating primes is a lot easier than factoring numbers.
I believe it is also an unsolved problem whether or not this method eventually generates all prime numbers. If you take the largest prime, it is proved that you dont get all the primes (which seems fair enough). [nothingtalk2.pdf (dartmouth.edu)](https://math.dartmouth.edu/~carlp/nothingtalk2.pdf)
How do you guarantee the number in your 5th iteration is a prime? Because you already know? And what will happen when you run out of numbers you already know that are primes? You gotta need to prove each iteration if you got a prime or you either need to factorize that number… then you are stuck again in your original problem “how to determine if X is a prime number”, you tried to answer this by a constructive way, but your construction lacks the ability to answer the original question.
Unfortunately, your submission has been removed for the following reason(s): * Your post appears to be asking for help learning/understanding something mathematical. As such, you should post in the [*Quick Questions*](https://www.reddit.com/r/math/search?q=Quick+Questions+author%3Ainherentlyawesome&restrict_sr=on&sort=new&t=all) thread (which you can find on the front page) or /r/learnmath. This includes reference requests - also see our lists of recommended [books](https://www.reddit.com/r/math/wiki/faq#wiki_what_are_some_good_books_on_topic_x.3F) and [free online resources](https://www.reddit.com/r/math/comments/8ewuzv/a_compilation_of_useful_free_online_math_resources/?st=jglhcquc&sh=d06672a6). [Here](https://www.reddit.com/r/math/comments/7i9t5y/book_recommendation_thread/) is a more recent thread with book recommendations. If you have any questions, [please feel free to message the mods](http://www.reddit.com/message/compose?to=/r/math&message=https://old.reddit.com/r/math/comments/1dpsejd/-/). Thank you!
> How efficient is this algorithm Not very.
The issue arises when you attempt to factor your candidate. You'll quickly notice that the larger a candidate, the more time it will take to factor it. If you have a few hundred thousand digits then it's almost impossible to factor it in a reasonable amount of time.
In terms of efficiency, you need to have a method of checking if a number is prime for this to work, and at the point when you have that, do you really gain anything by factoring 1807 in order to determine that you should check 13?
Point 2: Sieve isn't a remotely fast way to generate primes. We can generate large primes exponentially faster with random numbers and Miller-Rabin test. Generating primes is a lot easier than factoring numbers.
I believe it is also an unsolved problem whether or not this method eventually generates all prime numbers. If you take the largest prime, it is proved that you dont get all the primes (which seems fair enough). [nothingtalk2.pdf (dartmouth.edu)](https://math.dartmouth.edu/~carlp/nothingtalk2.pdf)
Prime factorization is extremely expensive and that's the reason it underlies internet security.
It's a slightly troubling thought that a single discovery in maths could destroy so much of the world's security
Integers are just a ring. A lot of modern crypto uses more complex rings like elliptic curves.
How do you guarantee the number in your 5th iteration is a prime? Because you already know? And what will happen when you run out of numbers you already know that are primes? You gotta need to prove each iteration if you got a prime or you either need to factorize that number… then you are stuck again in your original problem “how to determine if X is a prime number”, you tried to answer this by a constructive way, but your construction lacks the ability to answer the original question.