-4

我想使用有效的算法将主数存储在一个最多 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;
       }   
     }
4

6 回答 6

4

我假设您已经知道如何计算素数并且正在寻找一种紧凑的方式来存储它们。

如果“最有效”是指“压缩到尽可能小的空间”，那么有一种方法可以将素数存储在位数组中，该方法的位数大约是在位数组中存储真/假标志的一半。

诀窍是除了 2、3 和 5 之外的所有素数都是 30x 加上 1、7、11、13、17、19、23 或 29 的形式。因此，您可以将 1 到 30 的素数存储在一个字节中（忽略2, 3, 5)，然后是单个字节中从 31 到 60 的素数，然后是从 61 到 90 的素数，依此类推。您将不得不分别处理 2、3 和 5。

让我们以 67 为例。使用整数除法计算 67 / 30 = 2，因此您将查看素数指示字节数组的索引 2 处的字节。然后 67 - 30 * 2 = 7，这是字节的第二位，所以你看那里，找到一个 1，并得出结论 67 是素数。

使用这种方法，您可以将少于一百万的素数存储在 33,334 字节中。有关更多信息，请查看我的博客。

于 2013-04-09T16:14:58.613 回答
0

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.

于 2013-04-09T20:49:54.020 回答
0

作为数组中的每个整数都有 32 位。

所以你可以按照这个

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

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

更多的素数和更少的内存，您可以使用来自有效素数检查的阿特金筛子。

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

于 2013-04-09T19:10:47.047 回答
0

使用Set甚至List之类的集合。由于主要数字必须是唯一的，因此 Set 应该是显而易见的选择。

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

于 2013-04-09T15:52:15.783 回答
0 
// initialize list
ArrayList primes = new ArrayList();

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

// convert to primitive array  
primes.toArray();
于 2013-04-09T15:58:03.937 回答
0

2 和 3 也是素数：你想包括它们。

您可以通过使第二个循环迭代 whileO(n^2)来提高算法的复杂性。O(n^{3/2})j * j <= i

或者您可以使用Erastosthenes 筛，这将是O(n log log n)。

于 2013-04-09T15:58:36.983 回答