Method for generating prime numbers

Post Reply New Topic

Okay, I exaggerate a little. But just a little.

The difference between a finite time and infinity is not "a little".

I strongly suspect (over 99% certainty) that either you haven't done what you think you've done, or you don't understand what generating primes means. But I can't comment until you explain your idea.

Don't take this as in insult, it's just that you seem like an "amateur", and there are a lot of things you might have overlooked. Nothing wrong with amateurs! I'm glad that you're interested in this topic.

I appreciate your attitude and your skepticism. I am an amateur (from Latin
'amas' = "lover"). But I am a logician/linguist. My methods are to always simplify and to apply the simple methods to other problems. If I have discovered such a method, would it be valuable? And to whom?

Modern encryption often works like this: in order to decrypt a message without the "key", you need to be able to break down a huge number N as the product of two prime numbers. If you can quickly find large prime numbers, you can more easily find the prime factorisations of large numbers, so you can more easily decrypt information without the "key". Governments, security firms, they would all pay a lot of money for such a thing.

One, perhaps now not so, unfortunate consequence of my method is that it also generates some products of primes. This is what must be filtered out after generating the candidates.

See, I knew that there would be something like this.

The method by which you have to "filter out" the products of primes takes just as long as the Sieve of Eratosthenes. You have to go through all of the numbers you have generated, and check whether each is a prime or a product of primes. That's just as hard as the original problem!

I don't recall exactly, but I'm pretty sure these products are predictable. I discovered it a few months ago while playing with primes and didn't think a whole lot of it till I read a blog here on WP tonight that made me think it might be valuable. I need to sleep now, but I will look into it tomorrow.

Have a look at this:

http://www.cs.uwaterloo.ca/journals/JIS ... land21.pdf

ruveyn

i became interested in writing a simple code snippet to "generate" primes after i read this thread, but i can only "generate" primes at a rate of 2000 or so per second (displayed as printed on the screen with carriage returns between each number (which is obviously the most inefficient way (to just populate a database would be 200 times faster))) at the outset. obviously my program would get bogged down as the size of the numbers increases, as it does not "generate" primes, but it filters sequential numbers to establish if they are prime.

here is the code i wrote (i write my programs in visual foxpro).

SET TALK OFF
FOR X = 3 TO 100000000 STEP 2
MX=0
FOR Y = INT(X/2)-1 TO 3 STEP -1
IF X/Y = INT (X/Y)
MX=1
ENDIF
NEXT
IF MX=0
?X
ENDIF
NEXT


that is probably a very inefficient way of deriving primes, but my mental motherboard is not modern.

i can see how it is inefficient, because as the numbers grow, i do not need to ask the same questions with every iteration. it is more efficient than the most rudimentary methods because i obviously do not check even numbers or try to divide by numbers more than 1/2 the candidate -1.

here is a video of the program in operation, and i am not crowing about it because i hastily cobbled it together, and also, to print every result on screen takes vastly more time than it does to calculate the primes.

whatever. i stopped the program after a few seconds because you should get the idea, and it minimizes the size of the video file. it is a very simple program.

[youtube]http://www.youtube.com/watch?v=IHlQ3UGg3eo&feature=youtu.be[/youtube]

As you went on to say... you do not generate primes, but "prime candidates". I guess any odd number not ending in a digit 5 could be considered a prime candidate. You could then throw in stuff that avoided various other smallish prime factors.

OK. So could you give us a largish "prime candidate" and then show what you would do to establish whether it is really prime?

Here's a 21-digit prime candidate that I have come up with:

289582272970660878433

So... is it prime?

(and - it is too large for the *nix "factor" command to handle.)

Generating primes isn't worth anything, as far as I'm concerned. What is worth money is primes larger than the known primes, since they have great value in cryptology. If your method doesn't produce such numbers in human time, tough luck. Not that I believe in any worthwhile methods for doing such anyway.

I got the sieve working the fastest in Java, followed by dynamically testing with prime divisors only. Both got a some downsides, though I can't think of any way to improve them. They should both run in O(n * (primes of(sqrt(n)) or O(n*w(n^(1/2)), whichever notion is better. I run out of RAM when testing 1 billion numbers though. =/ I can post the code if you want. What bothers me the most is that it's hardware issues that makes it difficult to do brute force style.


Edit: Got 6 GB RAM, if each integer is 4 byte (not 2, oops), it should house an array of 1.5 billion integers if everything is allocated. Doesn't seem to quite work. 200 million run in just 4 seconds though (i7 3.0 GHz).
I asked it to print them as well, seems to be a bad idea. <.<

Since I'm not a mathematician, I'll use a naïve algorithm, illustrated in C:

That actually tests whether the arguments are prime or not. This one generates all the prime numbers from 1 to the first argument (inclusive). Again, it's a naïve, "brute-force" algorithm:

You can optimize it heavily by only searching up to the square root of the target, and by incrementing twice in the prime checker function itself, as it cuts the worst case down to 1/2 (worst case being a prime). Incrementing twice for checked values had little to no improvement on my java tests. :3
Also, if printf (don't know enough C) dumps the text in the terminal, it also slows down the process considerably.

So you are suggesting something like this?

I don't think saving the printing to STDOUT until after all the primes have been calculated buys much. I'm still printing the primes out after all the calculations are done (otherwise, how do you know the results?), but to store them, I'm using an array. Unlike Java, C does not have a built-in library of data structures/collections, so what I'm doing instead is allocating memory from the heap, and since I don't know how many primes there will be in advance, I'm just allocating an array of size maximum (corresponding to the maximum possible prime to generate to); obviously, when calculating up to larger primes, this could become prohibitive, so more complex memory management (e.g., using a smaller array size, reallocating when its limit has been reached, and copying the values over to the new array) would be needed. Obviously, storing the results in an array or other data structure makes them more accessible if we wanted to pass the primes to another function for further computation, but if we just want to show the user the results through STDOUT, storing the results to an array is probably not worth the trouble (in C at least).

In Java, things like java.util.ArrayList<?> and other java.util.Collection<?> use arrays or other less flexible data structures; they just handle the memory management for you. My day-to-day programming language at work is actually Java; I really don't work with C at all. I used C here since it's a sort of lingua franca in computing: It is a longstanding, internationally standardized (ISO/IEC 9899:1990 and subsequent revisions) programming language with compilers available on nearly every platform imaginable. Almost any architecture is going to have at least a basic C compiler with a fair chunk of the Standard C Library before it ever gets a Java compiler and virtual machine. Java's old slogan of, "Write once, run anywhere," is a bit of a fantasy. Today Java is quite popular for enterprise apps (that's what I get paid for) and on embedded/mobile devices, but it never really caught on on the desktop besides a fad for Java applets running in Web browsers for a few years in the late 1990s.

@lau: If your number isn't prime, it's got a really big prime factor. I messed around with factorizing in Haskell, since it has builtin support for arbitrary precision integers. After a couple of (not too tricky) optimizations, I got it to factor 433 factorial almost instantly, but that heavily depends on there being factors it can find fast. I also did 989582272970660878433, which has
919 and 27767 as factors. This is your number with a 9 instead of a 2 in the most significant place. It took about 15 seconds.

When I tried the number you gave, it ran for over 15 minutes before I killed it. If my guesses are right about how much time I save when I can find a relatively small factor (I then divide the number by the factor as many times as it will go, and recalculate the square root of this new number), then it would take at least 250 hours to finish running the program.