Веселье подсчета простых чисел

Question

Мы немного повеселимся здесь, на работе. Все началось с того, что один из парней создал Hackintosh, и нам было интересно, был ли он быстрее, чем Windows Box с (почти) теми же характеристиками, что и у нас. Поэтому мы решили написать небольшой тест для этого. Просто простой калькулятор простых чисел. Он написан на Java и сообщает нам время, необходимое для вычисления первых n простых чисел.

Оптимизированная версия ниже - теперь занимает ~ 6,6 сек

public class Primes {

    public static void main(String[] args) {
        int topPrime = 150000;
        int current = 2;
        int count = 0;
        int lastPrime = 2;

        long start = System.currentTimeMillis();

        while (count < topPrime) {

            boolean prime = true;

            int top = (int)Math.sqrt(current) + 1;

            for (int i = 2; i < top; i++) {
                if (current % i == 0) {
                    prime = false;
                    break;
                }
            }

            if (prime) {
                count++;
                lastPrime = current;
            }
            if (current == 2) {
             current++;
            } else {
                current = current + 2;
            }
        }

        System.out.println("Last prime = " + lastPrime);
        System.out.println("Total time = " + (double)(System.currentTimeMillis() - start) / 1000);
    } 
}

Мы в значительной степени потеряли сюжет всей игры Hackintosh против ПК и просто немного повеселились с ее оптимизацией. Первая попытка без оптимизации (у приведенного выше кода есть пара) длилась около 52,6 минут, чтобы найти первые 150000 простых чисел. Эта оптимизация выполняется за 47,2 минуты.

Если вы хотите проверить результаты и опубликовать результаты, вставьте их.

Характеристики ПК, на котором я работаю, - Pentium D 2,8 ГГц, 2 ГБ ОЗУ, Ubuntu 8.04.

Наилучшей оптимизацией до сих пор был квадратный корень тока, впервые упомянутый Джейсоном З.

Answer 1

Поскольку вы ищете их в порядке возрастания, вы можете хранить список простых чисел, которые вы уже нашли, и проверять только делимость на них, поскольку все не простые числа могут быть сведены к списку меньших простых факторы. Объедините это с предыдущим советом о том, что не нужно проверять факторы над корнем квадратным из текущего числа, и вы получите чертовски эффективную реализацию.

Answer 2

Это немного хуже, чем мое сито на 8 МГц 8088 в турбо паскале в 1986 году или около того. Но это было после оптимизаций:)

Answer 3

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

Вместо этого у вас есть только попытка до квадратного корня текущего числа.

И другая оптимизация была то, что BP сказал с изюминкой: Вместо

int count = 0;
...
for (int i = 2; i < top; i++)
...
if (current == 2)
  current++;
else
  current += 2;

использование

int count = 1;
...
for (int i = 3; i < top; i += 2)
...
current += 2;

Это должно значительно ускорить процесс.

Изменить:
Дополнительная оптимизация предоставлена ​​Джо Пинедой:
Удалите переменную "top".

int count = 1;
...
for (int i = 3; i*i <= current; i += 2)
...
current += 2;

Если эта оптимизация действительно увеличивает скорость до Java.
Расчет квадратного корня занимает много времени по сравнению с умножением двух чисел. Однако, поскольку мы перемещаем умножение в цикл for, это делается каждый отдельный цикл. Так что это МОЖЕТ замедлить работу в зависимости от того, насколько быстрым является алгоритм квадратного корня в Java.

Answer 4

Вот быстрое и простое решение:

• Нахождение простых чисел менее 100000; 9592 были найдены за 5 мс
• Нахождение простых чисел менее 1000000; 78498 были найдены за 20 мс
• Нахождение простых чисел менее 10000000; 664579 было найдено за 143 мс
• Нахождение простых чисел менее 100000000; 5761455 было найдено за 2024 мс

• Нахождение простых чисел меньше 1000000000; 50847534 было найдено за 23839 мс

  //returns number of primes less than n
  private static int getNumberOfPrimes(final int n)
  {
      if(n < 2) 
          return 0;
      BitSet candidates = new BitSet(n - 1);
      candidates.set(0, false);
      candidates.set(1, false);
      candidates.set(2, n);
      for(int i = 2; i < n; i++)
          if(candidates.get(i))
              for(int j = i + i; j < n; j += i)
                  if(candidates.get(j) && j % i == 0)
                      candidates.set(j, false);            
      return candidates.cardinality();
  }    
  

Answer 5

Нам понадобится меньше секунды (2,4 ГГц), чтобы сгенерировать первые 150000 простых чисел в Python с использованием Sieve of Eratosthenes:

#!/usr/bin/env python
def iprimes_upto(limit):
    """Generate all prime numbers less then limit.

    /136227/est-li-prostoi-algoritm-kotoryi-mozhet-opredelit-yavlyaetsya-li-prostym-ne-zaputat-prostogo-smertnogo-programmista#136256
    """
    is_prime = [True] * limit
    for n in range(2, limit):
        if is_prime[n]:
           yield n
           for i in range(n*n, limit, n): # start at ``n`` squared
               is_prime[i] = False

def sup_prime(n):
    """Return an integer upper bound for p(n).

       p(n) < n (log n + log log n - 1 + 1.8 log log n / log n)

       where p(n) is the n-th prime. 
       http://primes.utm.edu/howmany.shtml#2
    """
    from math import ceil, log
    assert n >= 13
    pn = n * (log(n) + log(log(n)) - 1 + 1.8 * log(log(n)) / log(n))
    return int(ceil(pn))

if __name__ == '__main__':
    import sys
    max_number_of_primes = int(sys.argv[1]) if len(sys.argv) == 2 else 150000
    primes = list(iprimes_upto(sup_prime(max_number_of_primes)))
    print("Generated %d primes" % len(primes))
    n = 100
    print("The first %d primes are %s" % (n, primes[:n]))

Пример:

$ python primes.py

Generated 153465 primes
The first 100 primes are [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 
127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,
199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379,
383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
467, 479, 487, 491, 499, 503, 509, 521, 523, 541]

Answer 6

В C #:

class Program
{
    static void Main(string[] args)
    {
        int count = 0;
        int max = 150000;
        int i = 2;

        DateTime start = DateTime.Now;
        while (count < max)
        {
            if (IsPrime(i))
            {
                count++;
            }

            i++;

        }
        DateTime end = DateTime.Now;

        Console.WriteLine("Total time taken: " + (end - start).TotalSeconds.ToString() + " seconds");
        Console.ReadLine();
    }

    static bool IsPrime(int n)
    {
        if (n < 4)
            return true;
        if (n % 2 == 0)
            return false;

        int s = (int)Math.Sqrt(n);
        for (int i = 2; i <= s; i++)
            if (n % i == 0)
                return false;

        return true;
    }
}

Выход:

Общее время: 2,087 секунды

Answer 7

Производится ли повторное объявление переменной prime

        while (count < topPrime) {

            boolean prime = true;

внутри цикла сделать его неэффективным? (Полагаю, это не имеет значения, поскольку я думаю, что Java оптимизирует это)

boolean prime;        
while (count < topPrime) {

            prime = true;

Answer 8

Помня о том, что есть лучшие способы поиска простых чисел ...

Я думаю, что вы можете взять этот цикл:

for (int i = 2; i < top; i++)

и сделайте так, чтобы ваша переменная-счетчик i выходила из 3 и пыталась сделать мод только на нечетных числах, поскольку все простые числа, кроме 2, никогда не делятся на четные числа.

Answer 9

Я нашел этот код где-то на моей машине, когда начал читать эту запись в блоге о простых числах. Код написан на C #, а алгоритм, который я использовал, пришел из моей головы, хотя, вероятно, он где-то в Википедии. ;) В любом случае, он может получить первые 150000 простых чисел за 300 мс. Я обнаружил, что сумма n первых нечетных чисел равна n ^ 2. Снова, вероятно, есть доказательство этого где-то в Википедии. Итак, зная это, я могу написать алгоритм, который никогда не должен будет вычислять квадратный корень, но я должен вычислять постепенно, чтобы найти простые числа. Так что если вы хотите N-е простое число, этот алгоритм должен будет найти (N-1) предшествующие простые числа раньше! Так и есть. Наслаждайтесь!

//
// Finds the n first prime numbers.
//
//count: Number of prime numbers to find.
//listPrimes: A reference to a list that will contain all n first prime if getLast is set to false.
//getLast: If true, the list will only contain the nth prime number.
//
static ulong GetPrimes(ulong count, ref IList listPrimes, bool getLast)
{
    if (count == 0)
        return 0;
    if (count == 1)
    {
        if (listPrimes != null)
        {
            if (!getLast || (count == 1))
                listPrimes.Add(2);
        }

        return count;
    }

    ulong currentSquare = 1;
    ulong nextSquare = 9;
    ulong nextSquareIndex = 3;
    ulong primesCount = 1;

    List dividers = new List();

    //Only check for odd numbers starting with 3.
    for (ulong curNumber = 3; (curNumber  (nextSquareIndex % div) == 0) == false)
                dividers.Add(nextSquareIndex);

            //Move to next square number
            currentSquare = nextSquare;

            //Skip the even dividers so take the next odd square number.
            nextSquare += (4 * (nextSquareIndex + 1));
            nextSquareIndex += 2;

            //We may continue as a square number is never a prime number for obvious reasons :).
            continue;
        }

        //Check if there is at least one divider for the current number.
        //If so, this is not a prime number.
        if (dividers.Exists(div => (curNumber % div) == 0) == false)
        {
            if (listPrimes != null)
            {
                //Unless we requested only the last prime, add it to the list of found prime numbers.
                if (!getLast || (primesCount + 1 == count))
                    listPrimes.Add(curNumber);
            }
            primesCount++;
        }
    }

    return primesCount;
}

Answer 10

Вот мой взгляд на это. Программа написана на языке C и занимает 50 миллисекунд на моем ноутбуке (Core 2 Duo, 1 ГБ Ram). Я сохраняю все вычисленные простые числа в массиве и пытаюсь делиться только до sqrt числа. Конечно, это не работает, когда нам нужно очень большое количество простых чисел (пробовал с 100000000), так как массив становится слишком большим и выдает ошибку сегмента.

/*Calculate the primes till TOTALPRIMES*/
#include <stdio.h>
#define TOTALPRIMES 15000

main(){
int primes[TOTALPRIMES];
int count;
int i, j, cpr;
char isPrime;

primes[0] = 2;
count = 1;

for(i = 3; count < TOTALPRIMES; i+= 2){
    isPrime = 1;

    //check divisiblity only with previous primes
    for(j = 0; j < count; j++){
        cpr = primes[j];
        if(i % cpr == 0){
            isPrime = 0;
            break;
        }
        if(cpr*cpr > i){
            break;
        }
    }
    if(isPrime == 1){
        //printf("Prime: %d\n", i);
        primes[count] = i;
        count++;
    }


}

printf("Last prime = %d\n", primes[TOTALPRIMES - 1]);
}

$ time ./a.out 
Last prime = 163841
real    0m0.045s
user    0m0.040s
sys 0m0.004s