Каков наиболее эффективный способ хранения простых чисел в массиве

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

Используйте коллекции как Set или даже List. Поскольку первичные номера должны быть уникальными, Set должен быть очевидным выбором.

Например: Set<Long> set = new HashSet<Long>();

Answer 2

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

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

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

Answer 3

2 и 3 также являются простыми: вы хотите, чтобы включить их.

Вы можете улучшить сложность своего алгоритма от O(n^2) до O(n^{3/2}), сделав повторение второго цикла в то время как j * j <= i.

Или вы можете использовать Sieve of Erastosthenes, который будет O(n log log n).

Answer 4

Я предполагаю, что вы уже знаете, как вычислить простые числа и ищете компактный способ их хранения.

Если «наиболее эффективный» означает «сжатый в наименьшее возможное пространство», существует метод, который хранит простые числа в битрейме, который составляет примерно половину битов, как только хранение флага true/false в bitarray.

Фокус в том, что все простые числа, за исключением 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 байт. Для получения дополнительной информации см. my blog.

Answer 5

AsEvery целое число в массиве имеет 32 бита.

Таким образом, вы можете следовать этому

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

Таким образом, вы устанавливаете на n-й бит как 1, что означает, что п является простым. Просто вы можете хранить

больше простых чисел с меньшим объемом памяти, и вы можете использовать сито Аткина из эффективной проверки.

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

Answer 6

Есть 9592 простые числа ниже 100000. Все номера ниже 100000 могут быть представлены в 17 bits (как 2^17 +131072). Кроме того, все простые числа, но простые 2 являются нечетными, и поэтому они должны иметь 0 в последнем бите, поэтому мы можем представить каждое штрихование ниже 100000 в 16 bits или 2 bytes. Итак, сделайте массив двойных байтов с нечетными штрихами 9591 и специальным правилом о простом 2. Это дает 19182 bytes данных.