# Prime Numbers

shmoe
Homework Helper
abertram28 said:
right now, there are no algorithmic methods of calculating primes, or obviously, we could just generate the largest ones quickly.

What do you mean by "calculate primes" here? There are plenty of agorithms that produce primes, maybe not as fast as we'd like but they are there.

abertram28 said:
wasnt there a proof that mersenne primes had to have a prime as an exponent? i cant remember where i saw that, but im pretty sure its true.

Yes, if the exponent is composite, say nm, just factor $$2^{nm}-1=(2^m)^n-1=(2^m-1)(2^{m(n-1)}+2^{m(n-2)}+\ldots+2^m+1)$$

there are algorithms that plug in single integers and ALWAYS produce primes? could you provide an example? im having trouble seeing that one being possible. i mean, i believe that one might be possible using a table of primes as input, but that isnt really an algorthim, unless the algorithm also produced those primes by the same process, starting with just 2 and 3. if so, id be very interested to play with it! does 1 count as a prime when starting these sequences? is 1 prime? im dumb.

ah, yes, ive actually used that factorization on the forms of the "odd perfect numbers", should they ever exist. thanks for that one.

Hurkyl
Staff Emeritus
Gold Member
Of course. For example, there is the algorithm that always returns "2". Another example is one that, given a positive integer n, it iterates through the integers bigger than n, testing each for primality, and returns the first that passes the test.

shmoe
Homework Helper
abertram28 said:
there are algorithms that plug in single integers and ALWAYS produce primes?

There are many, see http://mathworld.wolfram.com/PrimeFormulas.html for a few different ones. Some give only a subset of the primes, some give all primes. None are really convenient to work with though.

1 is generally not considered a prime these days.

ah, i see. none of these are basic algebraic algorithms. none of them are algebraic and use even a restricted input set! the iterative ones arent really even producing the prime, they are producing forms and testing for primality, its really a multifunction program rather than a single algorithm. but it still is an algorithm all on its own too. these really digress to the simple algorithm, if p=1, then n is prime; p=1 if n-PHI(n)=1. this is meaningless though, since its just a simple definition with a number theoretic function.

on 200 digit numbers, my calculator, TI-89 ti, displays F9 in raw data. its 155 digits or something. it also factors F6 pretty quickly. i mean, quickly for a handheld battery powered machine!

thanks for the prime formulas, ill be sure to print some of them and take them on my spring break road trip. it sucks that none of these are really useful. thats what i expected. none of these algorithms are really generators of primes, rather just indicators. i mean, as far as useful ones go. the simple number "2" being an algorithm is useless, though it might fit some arbitrary definition of algorithm.

mathwonk
Homework Helper
2020 Award
you seem to ignore the fact that these procedures do produce lots of large primes rather easily, even if they do not obey the rules you would like them to. the point is there is no problem about finding lots of large primes.

so you seem more interested in the process than the result?

hey, im not ignoring the fact that these procedures produce primes.
the fact that you think they are large and that the process is easy is opinion, nothing more. if some of these methods are capable of finding all the primes up to some "large prime" so easily, why do they have to include tests of primality? the algorithm either produces primes or it produces possible primes, and if it doesnt exclusively produce the inclusive list of primes without testing for primality as a part of the computation, it isnt that effective, else the largest prime known wouldnt have taken 50 days to compute, it would have just been generated easily.

im not sure how you deem that these algorithmic solutions that test for primality are "easy". im quite sure they are easy to understand, but easy to compute? hardly.

i am interested in the process, its the part that makes the procudure "easy" or "hard".
how can you claim the result is something that process is not? if the procedure is tedious, time consuming, and requires massive computing power, how can the result be "rather easy"? testing primality is pretty refined computing wise, but it still takes years to test 10 million digit numbers. they arent just generated, they are produced and then tested by these algorithmic solutions. the test isnt part of the algorithm really, since almost all of the primality tests are the standard test, Lucas set these out over a hundred years ago in basic form.

large is such a relative term, there will always be primes much larger than the ones we are currently testing, and so to say that these numbers are large assumes some initial frame. for me, that frame is referencing when it becomes quicker to look the number up in a table rather than test it. if the number has been tested once, its done. how do previous tests or any previous piece of information make these tests for primality faster based on a known prime table? as far as i know, the largest prime number known doesnt help in finding the next prime after it, and so the calculations always become increasingly tedious and time consuming. and thus, they cannot be easy when applied to something they need to do.

as long as the algorithm uses a test for primality or produces only known primes, its useless as far as technology or finding the next prime number.

i do, in fact, see a problem with finding lots of 10 million digit primes. its going to take forever just to test them, producing them is easy, producing them exclusively and inclusively is not. producing all of them without testing all of them is impossible. to me, that means the opposite of everything you just said.

*EDIT* let me add, that i think the current method for solving primality problems are quite elegant and efficient, my point is that there are always larger primes to be plugged and chugged, making the calculations always necessarily difficult and tedious. im a fan of the current methods. i never really mentioned any specific problem with the algorithms, aside from the fact that there isnt any use over the known basic forms of primes and a primality test. producing a number and testing a number through brute force are not the same thing, in my mind. producing a number and knowing its prime without testing it was my idea of a "prime producing algorithm" that produces all the primes as it goes up, such that no prime is left out. obviously there is the simple algorithm that just tests each number as you go up by 1. its not fast or easy. none of the mentioned algorithms are doing anything but eliminating numbers based on them being composite, and then doing the same exact thing as testing every single number. thus, they are not fast or easy either. just my opinion. please, watch your tone. is there a an algorithm that doesnt include testing for primality and gives a prime number of increasing size for each increased input?

i dont claim to be all knowing or even having an extensive knowledge on the subject. i do claim to know that the definitions of large are relative. even finding the primality of a mersenne, as you said one of the more easily determined primes, takes days and days when you look at unknown primes. none of these algorithms are faster than a table lookup until you get so large that neither a table lookup or an algorithm are all that quick. still, a table is much much faster. it cannot be said that these algorithmic methods produce large primes, lets use mersenne primes for example, quickly. it took two years with thousands of computers testing to find one, and that was in 1998. though computers are a lot faster today, so are the number of digits in the numbers we are testing. so, it can still be said, that the same methods that took tens of thousands of computers years to test enough to find one prime are in use today. another simple fact, you cant generate a mersenne prime of any given size, say with an exponent higher than the highest known prime, without first testing its exponent. this alone should stick out as a problem. without a table of known primes or without searching all these larege numbers for primes first, the next larger ones cannot even be generated. how that is fast and easy, is beyond me. *EDIT*

Last edited:
abertram28 said:
thanks for the prime formulas, ill be sure to print some of them and take them on my spring break road trip. it sucks that none of these are really useful.

Hurkyl gave you an outline for a useful algorithm to generate prime numbers with his second suggestion. One should see that, in principal, it's not too hard to generate "large" prime numbers if one has an efficient way to test for primality.

There is no shortage of papers and books which discuss methods for generating large prime numbers because methods like that are used all the time for cryptography applications.

Maybe you should read up on the subject of generating prime numbers before you tell us, again, that it's impossible.

exactly my point. if one has an efficient way to test for primality. that means that the algorithm isnt generating primes, but possible primes. simple as that. an equally useful algorithm is to take a=1, n=a-1, if a/n is an integer, a is not prime, else n=n-1 until n=2, if no n divides a, a is prime , a=a+1. this is nothing more than the basic definition of primality, and is NOT anything even remotely useful for generating primes.

i never said its impossible to generate primes. i said i didnt think there was an algorithm that generated ONLY primes that INCLUDED all the primes as it went up, and didnt require a primality test. those that require a primality test arent any more useful than just testing every number.

obviously the algorithms linked are much more complex than simply adding 1 and dividing by every smaller number. im not that stupid. but none of them are definately proven to produce every prime and only primes without testing for primality. primality test was the part that got me. more useful algorithms for GENERATING primes DONT involve testing some other generated number for primality. if they have to test the number, obviously the generator part of the algorithm ISNT producing primes, but only canidates.

as to hurkyls second suggestion, while a lot more useful than the algorithm "2", is still requiring testing for primality of a large group of numbers, and that is nothing worth being called fast or easy. in fact, since there is know known pattern, for extremely large numbers it could take an immense amount of time and effort.

Last edited:
abertram28 said:
exactly my point. if one has an efficient way to test for primality. that means that the algorithm isnt generating primes, but possible primes. simple as that.

But that's false.

abertram28 said:
i never said its impossible to generate primes.

What you said was:

"right now, there are no algorithmic methods of calculating primes"

but of course there are algorithmic methods for calculate primes.

let me refine the light of the context of my statement. obviously there are trivial solutions. its meaningless as a generator to use the algorithm "2" to generate primes.

the context was the generation of primes. if an algorithm tests for primality, reguardless of its method, it isnt generating primes, but generating numbers which may be prime. then the test is a second algorithm. to include a primality test in an algorithm for generating primes is pretty meaningless. any algorithm that tests for primality is automatically a "prime generating algorithm" according to you. well, it might be, but its a useless one, as it is neither fast nor easy.

so, just because one has a method for testing primes, in my humble opinion, does not give a prime number generator. the number generating portion of the algorithm is all thats concerned when the words NUMBER GENERATING ALGORITHM are used. NOT a number testing algorithm. the generating portion of all of these algorithms is NOT producing strictly primes, in any form. if the generation portion has the capability of producing a composite number, the generator isnt a prime number generator, but a prime canidate generator. if you want to say that a 'generating' algorithm is one that includes a 'testing' algorithm, go right ahead. generally, i said there are no algorithms that always give primes. in context, i meant useful ones that dont involve actual testing of a large portion of the generated numbers, that is, numbers generated by the generator portion of the algorithm, or the generator algorithm. i should have said that there are no generation algorithms for primes. because there arent. only testing ones. if one combines both, it still relies on testing primality, which isnt an easy task. generation algorithms would not eliminate any generated number as being composite. can you name any algorithm that doesnt directly test a number for primality? algorithms that involve testing, to me, are composite algorithms, using two very seperate algorithms, the generators and the testers. the two need not be connected. any generator could be used with any testing algorithm, and so, i see them as seperate. thats what i meant by calculate prime, not just 'find' a prime. brute force solutions are for babies.

Last edited:
abertram28 said:
so, just because one has a method for testing primes, in my humble opinion, does not give a prime number generator.

Your opinion of what it means for something to be a prime number generator is irrelevant. Any procedure that enumerates the prime numbers is a prime number generator; it doesn't matter how the procedure operates, or if it's inefficient. This is standard terminology. Definitions don't get changed every time someone complains that they should be different.

You seem to be interested in having a prime number generator faster than one that just interates over the integers and tests them for primality. So ask about that, instead of trying to change the meaning of "prime number generator" to exclude algorithms that aren't fast enough for you.

i wasnt trying to exclude ones that arent fast enough. i really dont care about the issue personally, but judging by the few of you who are posting, you must have some personal stake in this. why the attitude? did i step on someones toes in my first post? you could just kindly correct my terminology if you wanted.

any procedure that enumerates the prime numbers, while simple in defintion, is contextually meaninless. sure, there are plenty of useless algorithms for returning "2" no matter what you do. but they are contextually and physically meaninless, whether they fit the given definition. the defintion of generate has nowhere in it the "exhaustive exclusion" methods that testing algorithms have. so by definition, a generator should be the origin of the number, and the origin of the these numbers is NOT anywhere in the testing part of the algorithm. can you not admit that there are only one type of algorithm and that it is an algorithm for testing primality, not really for more specifically generating primes? the origin of the numbers, or the algorithm for generating numbers to be tested by the testing portion of the algorithm is more fitting of the defintion of "generator", so please link to your math dictionary so i can be more correct in terminology next time.

mathwonk was the one who claimed these methods to be fast and useful for generating large primes, which they certainly are not. while i have a passing interest in the topic, ill kindly use a lookup table if i need to use large primes for anything, rather than tediously generate them by exclusion algorithms.

what happened to the nice people here? did someone jade you all and make you necessarily evil? correcting someones terms is so commonplace, it shouldnt be done with such tone. i have no evil intent, so please dont make assumptions about my "seeming interest". i have none after these exchanges.

let me say, honestly, sorry if i hurt anyones feelings. maybe feelings arent the best thing to bring into a discussion like this. im not trying to redefine algorithm, or any other term. i thought maybe expressing my opinion would have been a good way to get it exactly clear. we can drop this part of the thread and let it continue normally... jeesh.

and, btw, there is really no such thing as a prime number generator through enumeration. there isnt even an enumeration algorithm for generating the integer set, so dont nitpick definitions too much. no enumerative process can create an infitine set, by definition, the process must take finite steps, and its quite obvious this generation of a complete set with infinite unique members cannot take place in finite steps.

Last edited:
abertram28 said:
i wasnt trying to exclude ones that arent fast enough. i really dont care about the issue personally, but judging by the few of you who are posting, you must have some personal stake in this. why the attitude? did i step on someones toes in my first post? you could just kindly correct my terminology if you wanted.

What's irritating people is that you obviously don't know what you're talking about and even after it's been pointed out that you're wrong, you carry on as if you've been right all along.

Here, let me use an analogy, maybe this will help you see what's going on.

Just because you might mean something different than everybody else when you use the word "flat" doesn't mean that it's an acceptable thing for you to say that "the earth is flat" on a scientific forum, and then for you to act surprised when everybody jumps in to tell you that it's wrong.

Saying that "the earth is flat" is just as ridiculous a thing to say as "there are no algorithms which generate prime numbers."

Last edited:
abertram28 said:
and, btw, there is really no such thing as a prime number generator through enumeration. there isnt even an enumeration algorithm for generating the integer set, so dont nitpick definitions too much. no enumerative process can create an infitine set, by definition, the process must take finite steps, and its quite obvious this generation of a complete set with infinite unique members cannot take place in finite steps.

It doesn't matter if we can't produce a listing of the entire set in a finite amount of time; we don't have anywhere to store an infinite amount of data anyway, so we don't want to produce an infinite set. All we need is some algorithm which is guaranteed to produce any specific member of a set in a finite amount of time.

As for my tone...if it bothers you that I called your opinion irrelevant, that's unfortunate, but it's true. I'm happy that you can admit that your complaint was only based on your personal opinion, but the impression I got from your post was that you thought saying that this was your opinion somehow lent more weight to what you were saying. If it bothers you that people would attack you personal opinion, then don't post your opinion on a discussion board.

Last edited:
mathwonk
Homework Helper
2020 Award
I suggest that this thread has become pointless.

mathwonk said:
I suggest that this thread has become pointless.

Agreed. It's turned into bickering over terminology.

I had trouble reading all three pages of this thread, but are you guys saying that prime numbers come in arbitrarily long, finite arithmetic progressions where it isn't always possible to predict the next number?

slackr007 said:
I had trouble reading all three pages of this thread, but are you guys saying that prime numbers come in arbitrarily long, finite arithmetic progressions where it isn't always possible to predict the next number?

Can the 'guy' who said "the prime numbers come in arbitrarily long, finite arithmetic progressions" pls tell me where u got that from? It would also be nice if you could tell me who proved that. Because i've never heard that prime numbers 'do' have any pattern whatsoever.

matt grime