Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Most efficient code for the first 10000 prime numbers?

I want to print the first 10000 prime numbers. Can anyone give me the most efficient code for this? Clarifications:

  1. It does not matter if your code is inefficient for n >10000.
  2. The size of the code does not matter.
  3. You cannot just hard code the values in any manner.
like image 741
Niyaz Avatar asked Aug 03 '08 05:08

Niyaz


People also ask

What is the most efficient prime number algorithm?

Sieve of Eratosthenes is a simple and ancient algorithm used to find the prime numbers up to any given limit. It is one of the most efficient ways to find small prime numbers. For a given upper limit n the algorithm works by iteratively marking the multiples of primes as composite, starting from 2.

What is the fastest way to figure out prime numbers?

To prove whether a number is a prime number, first try dividing it by 2, and see if you get a whole number. If you do, it can't be a prime number. If you don't get a whole number, next try dividing it by prime numbers: 3, 5, 7, 11 (9 is divisible by 3) and so on, always dividing by a prime number (see table below).


2 Answers

The Sieve of Atkin is probably what you're looking for, its upper bound running time is O(N/log log N).

If you only run the numbers 1 more and 1 less than the multiples of 6, it could be even faster, as all prime numbers above 3 are 1 away from some multiple of six. Resource for my statement

like image 126
Matt Avatar answered Sep 22 '22 21:09

Matt


I recommend a sieve, either the Sieve of Eratosthenes or the Sieve of Atkin.

The sieve or Eratosthenes is probably the most intuitive method of finding a list of primes. Basically you:

  1. Write down a list of numbers from 2 to whatever limit you want, let's say 1000.
  2. Take the first number that isn't crossed off (for the first iteration this is 2) and cross off all multiples of that number from the list.
  3. Repeat step 2 until you reach the end of the list. All the numbers that aren't crossed off are prime.

Obviously there are quite a few optimizations that can be done to make this algorithm work faster, but this is the basic idea.

The sieve of Atkin uses a similar approach, but unfortunately I don't know enough about it to explain it to you. But I do know that the algorithm I linked takes 8 seconds to figure out all the primes up to 1000000000 on an ancient Pentium II-350

Sieve of Eratosthenes Source Code: http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/

Sieve of Atkin Source Code: http://cr.yp.to/primegen.html

like image 28
num1 Avatar answered Sep 21 '22 21:09

num1