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

100000以下有9592个素数。100000以下的所有数字都可以用17 bits表示（因为2^17是131072）。此外，除了素数2之外，所有素数都是奇数，因此在最后一位将有一个0，因此我们可以在16 bits或2 bytes中表示低于100000的每个素数。所以，用9591个奇数素数和一个关于素数2的特殊规则来创建一个双字节数组。这提供了19182 bytes的数据

Answer 2

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

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

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

Answer 3

2和3也是素数：你想要包含它们

通过使第二个循环在j * j <= i时进行迭代，可以将算法的复杂度从O(n^2)提高到O(n^{3/2})

或者你可以使用Sieve of Erastosthenes，它将是O(n log log n)

Answer 4

使用像Set甚至List这样的集合。由于主要数字必须是唯一的，所以设置应该是显而易见的选择

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

Answer 5

数组中的每个整数都有32位

所以你可以跟着这个

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

这样就可以将第n位设置为1，这意味着n是素数。只要你能储存

更多的素数和更少的内存，你可以使用筛的阿特金从有效的素数检查

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