What is the most efficient way to store prime numbers in an array

Question

I want to store primary numbers in an array up-to n=100000 with an efficient algorithm.I am using the basic method to store prime numbers but it is taking more time.

       void primeArray(){
        int primes[100000],flag=0,k=2; 
        primes[0]=2;
        primes[1]=3;
        for(int i=5;i<n;i=i+2){
                for(int j=2;j<i/2;j++){
                    if(i%j==0){
                    flag=1;
                    break;
                   }
                }

            if(flag==0){
                primes[k]=i;
                k++;
            }

            flag=0;
       }   
     }

is this about storage of numbers? or about finding prime numbers? — Rylander, Apr 09 '13 at 15:51
Did you try googling "prime number algorithm" or something similar? — Code-Apprentice, Apr 09 '13 at 15:51
A downvote with no comment for the OP to work with :-(... @Sourabh, a lot has been written about efficient ways to find (probable) primes. Wikipedia's guide to [the Sieve of Eratosthenes](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) is a good place to start (but you'll to know a bit about mathematical modulus [not computing mod operator]). Perhaps this [SO post](http://stackoverflow.com/questions/453793/which-is-the-fastest-algorithm-to-find-prime-numbers) is more useful. — wmorrison365, Apr 09 '13 at 15:57
Please edit your question to specify that you are not looking to determine prime numbers, only to store numbers. — Rylander, Apr 09 '13 at 16:02
@MikeRylander: I think he wants a faster algorithm, and is just not expressing himself very clearly. — abeln, Apr 09 '13 at 16:04
@abeln his answer to the first comment says otherwise... but you might be right. — Rylander, Apr 09 '13 at 16:05

score 4 · Answer 1 · answered Apr 09 '13 at 16:14

I'm assuming you already know how to compute the primes and are looking for a compact way to store them.

If by "most efficient" you mean "compressed into the smallest possible space" there is a method that stores primes in a bitarray that is about half as many bits as just storing a true/false flag in a bitarray.

The trick is that all primes except 2, 3 and 5 are of the form 30x plus 1, 7, 11, 13, 17, 19, 23 or 29. Thus you can store the primes from 1 to 30 in a single byte (ignoring 2, 3, 5), then the primes from 31 to 60 in a single byte, then the primes from 61 to 90, and so on. You will have to handle 2, 3 and 5 separately.

Let's consider 67 as an example. Calculate 67 / 30 = 2 using integer division, so you will look at the byte at index 2 of the array of prime-indicating bytes. Then 67 - 30 * 2 = 7, which is the second bit of the byte, so you look there, find a 1, and conclude 67 is a prime.

With this approach, you can store the primes less than a million in 33,334 bytes. For more information, look at my blog.

These hints, they are very interesting! That sequence 6-4-2-4-2-4-6-2 can make the search for the next candidate prime number much faster than going 2 by 2 on odd numbers! As well as the eight primes in a byte approach make the representation very compact. I've made some experiments by putting those bytes in a Java BitSet. Thanks! — Jose Tepedino, Apr 10 '18 at 01:55

score 0 · Answer 2 · answered Apr 09 '13 at 15:52

0

Use collections like Set or even List. As primary numbers must be unique, Set should be the obvious choice.

Eg : Set<Long> set = new HashSet<Long>();

answered Apr 09 '13 at 15:52

Ankur Shanbhag

7,746
2
28
38

2

prime numbers are inherently ordered though, suggesting set might not be quite the right thing... – nbrooks Apr 09 '13 at 15:53

score 0 · Answer 3 · answered Apr 09 '13 at 15:58

0

// initialize list
ArrayList primes = new ArrayList();

// add another number
primes.add(newPrime);

// convert to primitive array  
primes.toArray();

answered Apr 09 '13 at 15:58

Rylander

19,449
25
93
144

score 0 · Answer 4 · answered Apr 09 '13 at 15:58

0

2 and 3 are also primes: you want to include them.

You can improve the complexity of your algorithm from O(n^2) to O(n^{3/2}) by making the second loop iterate while j * j <= i.

Or you can use the Sieve of Erastosthenes, which will be O(n log log n).

answered Apr 09 '13 at 15:58

abeln

3,749
2
22
31

`O(n * log log n)` for the Sieve of Eratosthenes. – Daniel Fischer Apr 09 '13 at 16:00
@DanielFischer: I stand corrected. Thanks! – abeln Apr 09 '13 at 16:01

score 0 · Answer 5 · answered Apr 09 '13 at 19:10

AsEvery integer in an array have 32 bits .

So you can follow this

if(isPrime(n))
a[n/32]=a[n/32]|(1<<(n%32));

This way you are setting the n'th bit as 1 , which means that n is prime . Just you can store

more primes with less memory and you can use sieve of Atkin from efficient prime checking .

http://en.wikipedia.org/wiki/Sieve_of_Atkin

score 0 · Answer 6 · answered Apr 09 '13 at 20:49

There are 9592 primes below 100000. All numbers below 100000 can be represented in 17 bits (as 2 ^ 17 is 131072). Furthermore, all primes but the prime 2 are odd, and therefor would have a 0 in the last bit - we can therefor represent each prime below 100000 in 16 bits or 2 bytes. So, make an array of double bytes with the 9591 odd primes and a special rule about the prime 2. This gives 19182 bytes of data.

What is the most efficient way to store prime numbers in an array

6 Answers6