1

i got follwoing question somewhere but not satisfied by my answer.

qtn: you have given a list of numbers that can be 10 billion numers. now you have to find out which are prime no among all of them.

I answered , to find a prime no we have to iterate through the loop for billion number and check one by one weather its prime or not . we can put some optimization check here if no is even we wil not check , since prime no can not be even. and to store the no we can use double array because double is size of 8 byte so it can handle billion number also. but still it seems he was not satisfied. please help here what could be more reasonable answer here. Thanks!

Prakash Raj
  • 11
  • 1
  • 2
  • Is this a Maths question? belongs to http://math.stackexchange.com – Raptor Oct 20 '14 at 09:19
  • 1
    what is the rangeof the 10 billion numbers? how large could the numbers be? – Sayakiss Oct 20 '14 at 09:20
  • 2
    checking if the number is even is not really an optimization, its the first step of the general check of whether the number is prime – yurib Oct 20 '14 at 09:21
  • 1
    Using a floating point array to store prime numbers is probably not a good idea. – tobias_k Oct 20 '14 at 09:23
  • 1
    A fast way to eliminate many of the numbers is the [Sieve of Eratosthenes](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes). – Tom Zych Oct 20 '14 at 09:29
  • look for isprime tests there are tons of them out there ... here: http://stackoverflow.com/a/22477240/2521214 is mine – Spektre Oct 20 '14 at 09:59
  • btw in interviews there is sometimes asking the right questions about your task more important then the answer itself... float/double numbers loose precision so you can not test big numbers properly, .... count of numbers isnot the same as their range btw – Spektre Oct 20 '14 at 10:05

1 Answers1

0

Let's say, we are storing the prime numbers in an array. According to Sieve of Eratosthenes:

  1. Create a list of consecutive integers from 2 through 10¹⁰: (2, 3, 4, ...., 10¹⁰).
  2. Initially, let p equal 2, the smallest prime number.
  3. Enumerate the multiples of p by counting to 10¹⁰ from 2p in increments of p, and mark them in the list (these will be 2p, 3p, 4p, ....; the p itself should not be marked).
  4. Insert p in the array.
  5. Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal to this new number (which is the next prime), and repeat from step 3.

When the algorithm terminates, you will have stored all the prime numbers below 10¹⁰ in the array.

Example

To find all the prime numbers less than or equal to 20, the procedure will be:

First generate a list of integers from 2 to 20:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

The first number in the list is 2; cross out every 2nd number in the list after 2 by counting up from 2 in increments of 2 (these will be all the multiples of 2 in the list):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

The next number in the list after 2 is 3; cross out every 3rd number in the list after 3 by counting up from 3 in increments of 3 (these will be all the multiples of 3 in the list):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

The next number not yet crossed out in the list after 3 is 5; cross out every 5th number in the list after 5 by counting from 5 in increments of 5 (i.e. all the multiples of 5), but they all have been crossed out at this point as these numbers (10, 15, 20) are also multiples of smaller primes because 5*5 is greater than 20. The numbers not crossed out in the list at this point are all the prime numbers below 20:

2 3     5    7           11       13              17      19

To make it more efficient, as you have said, you can initially list odd numbers only, (3, 5, ...., 10⁹), and count in increments of 2p from p² in step 3, thus marking only odd multiples of p.

Another way of making it efficient is to, mark the numbers in step 3 starting from p², as all the smaller multiples of p will have already been marked at that point. This means that the algorithm is allowed to terminate at step 5 when p² is greater than 10¹⁰.

You can also look up Segmented Sieve if you are low on memory and need to generate prime numbers in a smaller range.

Community
  • 1
  • 1
Bakhtiar Hasan
  • 889
  • 10
  • 25