1
$\begingroup$

The Sieve of Eratosthenes is an algorithm generate the prime numbers, $2,3,5,7,11,13,...$ by drawing a list of numbers crossing out multiples of the smallest number in the list.

Is there anyway to modify this algorithm to search for twin primes up to $N$?

One way would be to, generate the list of primes $p < \sqrt{N}$ and crossing out multiples of those primes should give prime numbers up to $N$. Then we can check $p \pm 2$ and see if they also appear in the list.

I posted a related question about whether we actually have to generate all primes for this task on cstheory.SE.

$\endgroup$
  • 4
    $\begingroup$ It sounds like you've answered your own question: the answer is yes, you can, by finding all prime numbers up to $N$, then for each prime $p$, checking $p+2$ to see if it also is in the list. So what's left to answer? What is the question? $\endgroup$ – D.W. Aug 15 '14 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.