What if I could generate an infinite number of primes from one prime almost instantly?
That's logically impossible. A program cannot generate an infinite number of primes in a finite amount of time. Think about it. Everytime the program outputs a prime, it takes some time to do so.
Joined: Dec 14, 2011 Posts: 111 Location: Missoula, MT
Posted: Mon Feb 13, 2012 4:05 am Post subject:
Declension wrote:
jackmt wrote:
What if I could generate an infinite number of primes from one prime almost instantly?
That's logically impossible. A program cannot generate an infinite number of primes in a finite amount of time. Think about it. Everytime the program outputs a prime, it takes some time to do so.
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.
Joined: Dec 14, 2011 Posts: 111 Location: Missoula, MT
Posted: Mon Feb 13, 2012 4:14 am Post subject:
Declension wrote:
jackmt wrote:
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?
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.
Joined: Dec 14, 2011 Posts: 111 Location: Missoula, MT
Posted: Mon Feb 13, 2012 4:28 am Post subject:
Declension wrote:
jackmt wrote:
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.
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!
Joined: Dec 14, 2011 Posts: 111 Location: Missoula, MT
Posted: Mon Feb 13, 2012 4:40 am Post subject:
Declension wrote:
jackmt wrote:
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.
Joined: Aug 15, 2008 Posts: 8357 Location: australia
Posted: Mon Feb 13, 2012 10:51 am Post subject:
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.
Joined: Jun 18, 2006 Age: 64 Posts: 10537 Location: Somerset UK
Posted: Mon Feb 13, 2012 6:00 pm Post subject:
jackmt wrote:
...
I looked up the Eratosthenes sieve, the Atkin(?) sieve, and the wheel sieve. They do not generate primes; they eliminate non-primes. I generate primes.
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.) _________________ "Striking up conversations with strangers is an autistic person's version of extreme sports." Kamran Nazeer
My method is better and more efficient. It does involve a two step filter after generating "prime candidates." It sounds like it may be valuable. Who should I see?
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. <.<
Joined: Jun 25, 2004 Posts: 5119 Location: St. Louis, Missouri
Posted: Mon Feb 13, 2012 8:55 pm Post subject:
Since I'm not a mathematician, I'll use a naïve algorithm, illustrated in C:
Code:
#include <stdlib.h>
#include <stdio.h>
typedef enum {FALSE, TRUE} BOOL;
BOOL test_factors(unsigned long factor, unsigned long integer)
{
BOOL result = TRUE;
if (factor < integer)
{
if (integer % factor == 0)
{
result = FALSE;
}
else
{
result = test_factors(++factor, integer);
}
}
return result;
}
BOOL prime(unsigned long integer)
{
return test_factors(2, integer);
}
int main(int argc, char* argv[])
{
int i = 0;
for (i = 1; i < argc; i++)
{
unsigned long number = strtoul(argv[i], NULL, 0);
if (number > 1)
{
if (prime(number))
{
printf("%lu is a prime number.\n", number);
}
else
{
printf("%lu is a composite number.\n", number);
}
}
else
{
printf("%s is not an integer greater than one.\n", argv[i]);
}
}
return EXIT_SUCCESS;
}
Joined: Jun 25, 2004 Posts: 5119 Location: St. Louis, Missouri
Posted: Mon Feb 13, 2012 9:10 pm Post subject:
NeantHumain wrote:
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:
Code:
#include <stdlib.h>
#include <stdio.h>
typedef enum {FALSE, TRUE} BOOL;
BOOL test_factors(unsigned long factor, unsigned long integer)
{
BOOL result = TRUE;
if (factor < integer)
{
if (integer % factor == 0)
{
result = FALSE;
}
else
{
result = test_factors(++factor, integer);
}
}
return result;
}
BOOL prime(unsigned long integer)
{
return test_factors(2, integer);
}
int main(int argc, char* argv[])
{
if (argc > 1)
{
unsigned long maximum = strtoul(argv[1], NULL, 0);
if (maximum > 1)
{
printf("2\n");
unsigned long i = 0;
for (i = 3; i <= maximum; i += 2)
{
if (prime(i))
{
printf("%lu\n", i);
}
}
}
}
return EXIT_SUCCESS;
}
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.
