java - 素数を配列に格納する最も効率的な方法は何ですか?

Question

効率的なアルゴリズムで n=100000 までの配列に素数を格納したい.素数を格納する基本的な方法を使用していますが、時間がかかります.

       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;
       }   
     }

Answer 1

配列内のすべての整数は 32 ビットです。

だからあなたはこれに従うことができます

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

このようにして、n 番目のビットを 1 に設定します。これは、 n が素数であることを意味します。あなただけが収納できます

より少ないメモリで素数を増やし、効率的な素数チェックから Atkin のふるいを使用できます。

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

Answer 2

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

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

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

Answer 3

SetやListなどのコレクションを使用します。基本番号は一意でなければならないため、Set を選択するのは当然のことです。

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