Any composite number N has a divisor less than or equal to sqrt(N) so you don''t have to test every single number, but still a whole lot of them.
Someone recently discovered an "efficient" primality test. I say "efficient" because although its complexity is polynomial it''s still EXTREMELY slow for large primes.
Primes
I don''t think you can corner the market on memory for $100k. I could be wrong, but isn''t log(log(10^10^6))=6? So even if that was only bytes does the world even have 1/6*10^1000000 bytes of memory. Say the average computer had 10^10 bytes of memory, every person had 10^5 computers and you had 10^10 people then you would only have 3/20000th of the memory you would need.
Sorry, spending too much time around engineers.
Sorry, spending too much time around engineers.
Author
Couldn''t you re-use memory from the first 300,000,000 to calculate the second batch?
I suppose there''s a way to overlap the numbers in memory, to save all the preceding zeros.
Also, since all but one of the primes is odd, the lowest bit can be assumed to be one, and discarded. After you''ve calculated 300,000,000 primes, you can free up enough space to store another number up to 2^300000000
********
A Problem Worthy of Attack
Proves It''s Worth by Fighting Back
I suppose there''s a way to overlap the numbers in memory, to save all the preceding zeros.
Also, since all but one of the primes is odd, the lowest bit can be assumed to be one, and discarded. After you''ve calculated 300,000,000 primes, you can free up enough space to store another number up to 2^300000000
********
A Problem Worthy of Attack
Proves It''s Worth by Fighting Back
Prime Info
Hey, I just started playing around with primes myself. Hope some of this site's info will be useful to some people here.
Good Luck finding a 100% proven why of generating huge primes quickier then modern methods.;P
the cheesy algo for finding the small primes I use is:
Primes can be fun to fight with looking for crazy patterns and certainties. Someday I hope to understand enough to make some sort of contribution to the discovery of huge primes.
[edited by - CodeJunkie on February 8, 2003 6:46:29 AM]
Hey, I just started playing around with primes myself. Hope some of this site's info will be useful to some people here.
Good Luck finding a 100% proven why of generating huge primes quickier then modern methods.;P
the cheesy algo for finding the small primes I use is:
// primes array is global with 8000 element max for nowunsigned char PG_Primes_Squared(unsigned long int max_number, unsigned char Flag_MakeFile){ unsigned long int i,j,square_root,prime_squared; unsigned long int primes_found=0; FILE *fptr_primes=0; // Create/Override File if(!(fptr_primes=fopen("primes.txt","w+t"))) {// File was not created printf("\n\n!!!File could not be created!!!\n\n"); printf("\n\nPress a key to exit...\n"); getch(); return(0); } // put the first two known primes in the list fprintf(fptr_primes,"List of Primes\n---------------\n"); primes[0]=2;primes[1]=3; primes_found=2;// generate the primesprime_squared = primes[1] * primes[1];square_root = 1;for(i=5;i<=max_number;i+=2) // only step through the odds{ // when the numbers become greater than the currently used squared prime use the next if(prime_squared<i) {square_root++; prime_squared = primes[square_root] * primes[square_root]; printf("."); } // using the square of the primes to limit the tested primes j=1; // no need to divide by 2 because only odds are tested while((j<=square_root)&&(i%primes[j]!=0)){j++;} // Check if prime was found // basically if (j-1 == square_root) then the number couldn't be divided // by the primes if((--j)==square_root) {//prime was found if(primes_found<8000){primes[primes_found] = i;} primes_found++; }}// Print the primes into the fileif(Flag_MakeFile){ for(i=0;i<primes_found;i++) { if(i<8000){fprintf(fptr_primes,"%u]. %u\n",i+1,primes[i]);} }} // Display results printf("\n\nResults\n--------\n"); printf(" %u Primes found.\n Largest prime used to factor was %u. The %uth prime found.\n",primes_found,primes[square_root],square_root+1); printf("\n"); // End of PG_Primes_Squared fclose(fptr_primes); return(1);} Primes can be fun to fight with looking for crazy patterns and certainties. Someday I hope to understand enough to make some sort of contribution to the discovery of huge primes.
[edited by - CodeJunkie on February 8, 2003 6:46:29 AM]
Actually, the price is for a 10 million digit prime. A 4 million digit prime has already been found (2^13466917-1).
Author
Going back to the original, let Pn be the highest found prime
The product of all primes up to Pn, plus one, is either prime or the product of much larger primes.
let An be the product of the first n primes, and B be P(n+1)
A(n+1)=An*P(n+1)
P(n+2)=A(n+1)+1
Since this only requires memory for storing 2 numbers, there shouldn''t be a problem finding Pm 10 million digits long. Since Pm is likely to be prime, won''t this be a relativly fast, considering many primes are skipped?
********
A Problem Worthy of Attack
Proves It''s Worth by Fighting Back
The product of all primes up to Pn, plus one, is either prime or the product of much larger primes.
let An be the product of the first n primes, and B be P(n+1)
A(n+1)=An*P(n+1)
P(n+2)=A(n+1)+1
Since this only requires memory for storing 2 numbers, there shouldn''t be a problem finding Pm 10 million digits long. Since Pm is likely to be prime, won''t this be a relativly fast, considering many primes are skipped?
********
A Problem Worthy of Attack
Proves It''s Worth by Fighting Back
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
