Забава вычисления простого числа

Вот является мое решение... своим довольно быстрым... оно вычисляет начала между 1 и 10,000,000 за 3 секунды на моей машине (Core i7 2.93 ГГц) на 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;
}

Я решил попробовать это в F#, моей первой достойной попытке его. Используя Решето Эратосфена на моем Core 2 Duo на 2.2 ГГц это пробегает 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

Я держал пари, что Miller-Rabin будет быстрее. При тестировании достаточного количества непрерывных чисел, это становится детерминированным, но я даже не обеспокоился бы. После того как рандомизированный алгоритм достигает точки, что ее интенсивность отказов равна вероятности, что отклонение ЦП вызовет неправильный результат, это просто не имеет значения больше.

Необходимо смочь сделать внутренний цикл вдвое более быстрым, только оценив нечетные числа. Не уверенный, если это - допустимый 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;
                            }
                    }
            }

Мое взятие при оптимизации, избегая слишком загадочных приемов. Я использую прием, данный 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

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

Делает переобъявление переменного начала

        while (count < topPrime) {

            boolean prime = true;

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

boolean prime;        
while (count < topPrime) {

            prime = true;

C#

Улучшение к коду Aistina:

Это использует то, что все начала, больше, чем 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;
    }
}

Учет того факта, что существуют лучшие способы искать начала...

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

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

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

В 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 секунды

Это берет нас под секундой (2.4 ГГц) для генерации первых 150 000 простых чисел в Python с помощью Решета Эратосфена:

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

    http://stackoverflow.com/questions/188425/project-euler-problem#193605
    """
    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]

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

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

@ Mark Ransom - не уверен, что это 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 ....
      }

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

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

patch (плюс добавить 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

Вот мой взгляд на это. Программа написана на C и занимает 50 миллисекунд на моем ноутбуке (Core 2 Duo, 1 ГБ оперативной памяти). Я сохраняю все вычисленные простые числа в массиве и пытаюсь делить только до 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

Я нашел этот код где-то на своей машине, когда начал читать эту запись в блоге о простых числах. Код написан на 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;
}