# Breaking the code - How to determine large and very large Primes?

A discussion on how to determine large and very large primes from the context of Number Theory.

## Monday, January 25, 2010

### Breaking the Code Part 2 - Which is which? The Sieve Algorithms or The Primality Test Equations

Issue: Breaking the Code Part 2 -Which is which? The Sieve Algorithms or The Primality Test Equations

Yes, I agree with Mr. Jay that the modern sieve of Atkin is more complicated, but
faster when properly optimized. Atkin's algorithm is actually more efficient than the sieve of eratosthenes when run in computers. This is somehow due to the fact the algorithm takes less memory of the computer than its predecessor the sieve of eratosthenes. This can be proven by the statement from Wikipedia that the Atkin sieve computes primes up to N using O(N/log log N) operations with only N1/2 + o(1) bits of memory. That is a little better than the sieve of Eratosthenes which uses O(N) operations and O(N1/2(log log N)/log N) bits of memory. However, this does not amplify so much for there is only minor advantage when both are compared. But, what I am quite unsure of, is the findings of my pal that the sieve of Eratosthenes is useful only for relatively small primes.

Before we further our discussion, friends, may I know your opinions on the following questions:

1. "Which is better?" - Which do you think is better in finding the large or very large primes: The algorithm method? or Is it the use of primality test equations?

2. "How large is your large?" - How large is your large prime that you think this is the largest prime?

3. "How fast are you?" - Which do you is more faster, the manual method or the computer generated method of locating prime?

References:

Jay08_20, [usepmat_group]primes, 1/19/2010   , 

http://en.wikipedia.org/wiki/Sieve_of_Atkin, (Date accessed: 01/19/2010)   

http://stackoverflow.com/questions/622/most-efficient-code-for-the-first-10000-prime-numbers