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

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

@ Марк Рэнсом - не уверен, что это код Java

Они будут стонать возможно , но я хотел переписать, используя парадигму, которую я научился доверять Java, и они сказали, что повеселиться, пожалуйста, убедитесь, что они понимают, что спецификация ничего не говорит, что влияет на порядок в возвращаемом набор результатов, также вы должны преобразовать значения точек набора результатов () в тип списка, указанный в блокноте, перед тем как выполнить короткое поручение

=============== начать непроверенный код ===============

package demo;

import java.util.List;
import java.util.HashSet;

class Primality
{
  int current = 0;
  int minValue;
  private static final HashSet<Integer> resultSet = new HashSet<Integer>();
  final int increment = 2;
  // An obvious optimization is to use some already known work as an internal
  // constant table of some kind, reducing approaches to boundary conditions.
  int[] alreadyKown = 
  {
     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
  };
  // Trivial constructor.

  public Primality(int minValue)
   {
      this.minValue = minValue;
  }
  List calcPrimes( int startValue )
  {
      // eliminate several hundred already known primes 
      // by hardcoding the first few dozen - implemented 
      // from prior work by J.F. Sebastian
      if( startValue > this.minValue )
      {
          // Duh.
          current = Math.abs( start );
           do
           {
               boolean prime = true;
               int index = current;
               do
               {
                  if(current % index == 0)
                  {
                      // here, current cannot be prime so break.
                      prime = false;
                      break;
                   }
               while( --index > 0x00000000 );

               // Unreachable if not prime
               // Here for clarity

               if ( prime )
               {     
                   resultSet dot add ( or put or whatever it is )
                           new Integer ( current ) ;
               }
           }
           while( ( current - increment ) > this.minValue );
           // Sanity check
           if resultSet dot size is greater that zero
           {
              for ( int anInt : alreadyKown ) { resultSet.add( new Integer ( anInt ) );}
             return resultSet;
           }
           else throw an exception ....
      }

=============== конец непроверенного кода ===============

Использование хэш-наборов позволяет искать результаты в виде B-деревьев, поэтому результаты могут накапливаться до тех пор, пока машина не начнет выходить из строя, тогда эту начальную точку можно использовать для другого блока тестирования == конец одного прогона, используемого в качестве значения конструктора для другого запуска - сохранение работы диска, уже выполненной, и допущение дополняющего проектирования с прямой связью. Сгорел прямо сейчас, логика цикла нуждается в анализе.

исправление (плюс добавление sqrt):

  if(current % 5 == 0 )
  if(current % 7 == 0 )
  if( ( ( ( current % 12 ) +1 ) == 0) || ( ( ( current % 12 ) -1 ) == 0) ){break;}
  if( ( ( ( current % 18 ) +1 ) == 0) || ( ( ( current % 18 ) -1 ) == 0) ){break;}
  if( ( ( ( current % 24 ) +1 ) == 0) || ( ( ( current % 24 ) -1 ) == 0) ){break;}
  if( ( ( ( current % 36 ) +1 ) == 0) || ( ( ( current % 36 ) -1 ) == 0) ){break;}
  if( ( ( ( current % 24 ) +1 ) == 0) || ( ( ( current % 42 ) -1 ) == 0) ){break;}


// and - new work this morning:


package demo;

/**
 *
 * Buncha stuff deleted for posting .... duh.
 *
 * @author  Author
 * @version 0.2.1
 *
 * Note strings are base36
 */
public final class Alice extends java.util.HashSet<java.lang.String>
{
    // prints 14551 so it's 14 ½ seconds to get 40,000 likely primes
    // using Java built-in on amd sempron 1.8 ghz / 1600 mhz front side bus 256 k L-2
    public static void main(java.lang.String[] args)
    {
        try
        {
            final long start=System.currentTimeMillis();
            // VM exhibits spurious 16-bit pointer behaviour somewhere after 40,000
            final java.lang.Integer upperBound=new java.lang.Integer(40000);
            int index = upperBound.intValue();

            final java.util.HashSet<java.lang.String>hashSet
            = new java.util.HashSet<java.lang.String>(upperBound.intValue());//
            // Arbitraily chosen value, based on no idea where to start.
            java.math.BigInteger probablePrime
            = new java.math.BigInteger(16,java.security.SecureRandom.getInstance("SHA1PRNG"));
            do
            {
                java.math.BigInteger nextProbablePrime = probablePrime.nextProbablePrime();
                if(hashSet.add(new java.lang.String(nextProbablePrime.toString(Character.MAX_RADIX))))
                {
                    probablePrime = nextProbablePrime;
                    if( ( index % 100 ) == 0x00000000 )
                    {
                        // System.out.println(nextProbablePrime.toString(Character.MAX_RADIX));//
                        continue;
                    }
                    else
                    {
                        continue;
                    }
                }
                else
                {
                    throw new StackOverflowError(new String("hashSet.add(string) failed on iteration: "+
                    Integer.toString(upperBound.intValue() - index)));
                }
            }
            while(--index > 0x00000000);
            System.err.println(Long.toString( System.currentTimeMillis() - start));
        }
        catch(java.security.NoSuchAlgorithmException nsae)
        {
            // Never happen
            return;
        }
        catch(java.lang.StackOverflowError soe)
        {
            // Might happen
            System.out.println(soe.getMessage());//
            return;
        }
    }
}// end class Alice

Answer 2

Вот мое решение ... оно довольно быстрое ... оно вычисляет простые числа от 1 до 10 000 000 за 3 секунды на моей машине (core i7 @ 2.93Ghz) на Vista64.

Мое решение на C, но я не профессиональный программист на C. Не стесняйтесь критиковать алгоритм и сам код:)

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>

//5MB... allocate a lot of memory at once each time we need it
#define ARRAYMULT 5242880 


//list of calculated primes
__int64* primes; 
//number of primes calculated
__int64 primeCount;
//the current size of the array
__int64 arraySize;

//Prints all of the calculated primes
void PrintPrimes()
{
    __int64 i;
    for(i=0; i<primeCount; i++)
    {
        printf("%d ", primes[i]);
    }

}

//Calculates all prime numbers to max
void CalcPrime(__int64 max)
{
    register __int64 i;
    double square;
    primes = (__int64*)malloc(sizeof(__int64) * ARRAYMULT);
    primeCount = 0;
    arraySize = ARRAYMULT;

    //we provide the first prime because its even, and it would be convenient to start
    //at an odd number so we can skip evens.
    primes[0] = 2;
    primeCount++;



    for(i=3; i<max; i+=2)
    {
        int j;
        square = sqrt((double)i);

        //only test the current candidate against other primes.
        for(j=0; j<primeCount; j++)
        {
            //prime divides evenly into candidate, so we have a non-prime
            if(i%primes[j]==0)
                break;
            else
            {
                //if we've reached the point where the next prime is > than the square of the
                //candidate, the candidate is a prime... so we can add it to the list
                if(primes[j] > square)
                {
                    //our array has run out of room, so we need to expand it
                    if(primeCount >= arraySize)
                    {
                        int k;
                        __int64* newArray = (__int64*)malloc(sizeof(__int64) * (ARRAYMULT + arraySize));

                        for(k=0; k<primeCount; k++)
                        {
                            newArray[k] = primes[k];
                        }

                        arraySize += ARRAYMULT;
                        free(primes);
                        primes = newArray;
                    }
                    //add the prime to the list
                    primes[primeCount] = i;
                    primeCount++;
                    break;

                }
            }

        }

    }


}
int main()
{
    int max;
    time_t t1,t2;
    double elapsedTime;

    printf("Enter the max number to calculate primes for:\n");
    scanf_s("%d",&max);
    t1 = time(0);
    CalcPrime(max);
    t2 = time(0);
    elapsedTime = difftime(t2, t1);
    printf("%d Primes found.\n", primeCount);
    printf("%f seconds elapsed.\n\n",elapsedTime);
    //PrintPrimes();
    scanf("%d");
    return 1;
}

Answer 3

Бьюсь об заклад, Миллер-Рабин будет быстрее. Если вы протестируете достаточно смежные числа, это станет детерминированным, но я бы даже не стал беспокоиться. Как только рандомизированный алгоритм достигнет точки, в которой частота отказов будет равна вероятности того, что сбой процессора вызовет неправильный результат, это уже не имеет значения.

Answer 4

Вы должны быть в состоянии сделать внутренний цикл в два раза быстрее, вычисляя только нечетные числа. Не уверен, что это допустимая Java, я привык к C ++, но я уверен, что она может быть адаптирована.

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

Answer 5

Мой взгляд на оптимизацию, избегая слишком загадочных уловок. Я использую трюк, данный I-GIVE-TERRIBLE-ADVICE, который я знал и забыл ...: -)

public class Primes
{
  // Original code
  public static void first()
  {
    int topPrime = 150003;
    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;
//      System.out.print(lastPrime + " "); // Checking algo is correct...
      }
      if (current == 2) {
        current++;
      } else {
        current = current + 2;
      }
    }

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

  // My attempt
  public static void second()
  {
    final int wantedPrimeNb = 150000;
    int count = 0;

    int currentNumber = 1;
    int increment = 4;
    int lastPrime = 0;

    long start = System.currentTimeMillis();

NEXT_TESTING_NUMBER:
    while (count < wantedPrimeNb)
    {
      currentNumber += increment;
      increment = 6 - increment;
      if (currentNumber % 2 == 0) // Even number
        continue;
      if (currentNumber % 3 == 0) // Multiple of three
        continue;

      int top = (int) Math.sqrt(currentNumber) + 1;
      int testingNumber = 5;
      int testIncrement = 2;
      do
      {
        if (currentNumber % testingNumber == 0)
        {
          continue NEXT_TESTING_NUMBER;
        }
        testingNumber += testIncrement;
        testIncrement = 6 - testIncrement;
      } while (testingNumber < top);
      // If we got there, we have a prime
      count++;
      lastPrime = currentNumber;
//      System.out.print(lastPrime + " "); // Checking algo is correct...
    }

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

  public static void main(String[] args)
  {
    first();
    second();
  }
}

Да, я использовал метку продолжения, когда я впервые пробую их на Java ...
Я знаю, что пропускаю вычисления первых нескольких простых чисел, но они общеизвестны, нет смысла их пересчитывать. :-) Я могу жестко запрограммировать их вывод при необходимости! Кроме того, это не дает решающего преимущества в любом случае.

Результаты:

- Первый
Последний штрих = 2015201
Общее время = 4,281

- Второй
Последний штрих = 2015201
Общее время = 0,953

Неплохо. Полагаю, можно немного улучшить, но слишком большая оптимизация может убить хороший код.

Answer 6

C #

Расширение до Код Айстины :

Здесь используется тот факт, что все простые числа больше 3 имеют форму 6n + 1 или 6n - 1.

Это было увеличение скорости примерно на 4-5% по сравнению с увеличением на 1 для каждого прохода через цикл.

class Program
{       
    static void Main(string[] args)
    {
        DateTime start = DateTime.Now;

        int count = 2; //once 2 and 3

        int i = 5;
        while (count < 150000)
        {
            if (IsPrime(i))
            {
                count++;
            }

            i += 2;

            if (IsPrime(i))
            {
                count++;
            }

            i += 4;
        }

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

Answer 7

Вот мой вклад:

Машина: 2,4 ГГц Quad-Core i7 с 8 ГБ оперативной памяти @ 1600 МГц

Компилятор: clang++ main.cpp -O3

Тесты:

Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 100

Calculated 25 prime numbers up to 100 in 2 clocks (0.000002 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 1000

Calculated 168 prime numbers up to 1000 in 4 clocks (0.000004 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 10000

Calculated 1229 prime numbers up to 10000 in 18 clocks (0.000018 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 100000

Calculated 9592 prime numbers up to 100000 in 237 clocks (0.000237 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 1000000

Calculated 78498 prime numbers up to 1000000 in 3232 clocks (0.003232 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 10000000

Calculated 664579 prime numbers up to 10000000 in 51620 clocks (0.051620 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 100000000

Calculated 5761455 prime numbers up to 100000000 in 918373 clocks (0.918373 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 1000000000

Calculated 50847534 prime numbers up to 1000000000 in 10978897 clocks (10.978897 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ ./a.out 4000000000

Calculated 189961812 prime numbers up to 4000000000 in 53709395 clocks (53.709396 seconds).
Caelans-MacBook-Pro:Primer3 Caelan$ 

Источник:

#include <iostream> // cout
#include <cmath> // sqrt
#include <ctime> // clock/CLOCKS_PER_SEC
#include <cstdlib> // malloc/free

using namespace std;

int main(int argc, const char * argv[]) {
    if(argc == 1) {
        cout << "Please enter a number." << "\n";
        return 1;
    }
    long n = atol(argv[1]);
    long i;
    long j;
    long k;
    long c;
    long sr;
    bool * a = (bool*)malloc((size_t)n * sizeof(bool));

    for(i = 2; i < n; i++) {
        a[i] = true;
    }

    clock_t t = clock();

    sr = sqrt(n);
    for(i = 2; i <= sr; i++) {
        if(a[i]) {
            for(k = 0, j = 0; j <= n; j = (i * i) + (k * i), k++) {
                a[j] = false;
            }
        }
    }

    t = clock() - t;

    c = 0;
    for(i = 2; i < n; i++) {
        if(a[i]) {
            //cout << i << " ";
            c++;
        }
    }

    cout << fixed << "\nCalculated " << c << " prime numbers up to " << n << " in " << t << " clocks (" << ((float)t) / CLOCKS_PER_SEC << " seconds).\n";

    free(a);

    return 0;
}

При этом используется подход Sieve of Erastothenes, я максимально оптимизировал его, насколько смог. Улучшения приветствуются.

Answer 8

Я решил попробовать это в F #, моей первой приличной попытке. Используя сито эратосфена на моем 2,2 ГГц Core 2 Duo, он проходит через 2,150 000 примерно за 200 миллисекунд. Каждый раз, когда он называет себя сам, он удаляет текущие кратные значения из списка, поэтому он просто становится быстрее по мере продвижения. Это одна из моих первых попыток в F #, поэтому любые конструктивные комментарии приветствуются.

let max = 150000
let numbers = [2..max]
let rec getPrimes sieve max =
    match sieve with
    | [] -> sieve
    | _ when sqrt(float(max)) < float sieve.[0] -> sieve
    | _ -> let prime = sieve.[0]
           let filtered = List.filter(fun x -> x % prime <> 0) sieve // Removes the prime as well so the recursion works correctly.
           let result = getPrimes filtered max
           prime::result        // The filter removes the prime so add it back to the primes result.

let timer = System.Diagnostics.Stopwatch()
timer.Start()
let r = getPrimes numbers max
timer.Stop()
printfn "Primes: %A" r
printfn "Elapsed: %d.%d" timer.Elapsed.Seconds timer.Elapsed.Milliseconds