performance - 제너레이터 - 코드리뷰란




첫 10000 소수에 가장 효율적인 코드? (20)

첫 10000 소수를 인쇄하고 싶습니다. 누구든지 이것을 위해 가장 효율적인 코드를 줄 수 있습니까? 설명 :

  1. n> 10000에 대해 코드가 비효율적인지 여부는 중요하지 않습니다.
  2. 코드의 크기는 중요하지 않습니다.
  3. 어떤 방식 으로든 값을 하드 코딩 할 수는 없습니다.

Javascript에서 Array.prototype.find () 메소드 사용 2214.486ms

function isPrime (number) {

  function prime(element) {
    let start = 2;
    while (start <= Math.sqrt(element)) {
      if (element % start++ < 1) {
        return false;
      }
    }
    return element > 1;
  }

  return [number].find(prime)

}

function logPrimes (n) {

  let count = 0
  let nth = n

  let i = 0
  while (count < nth) {
    if (isPrime(i)) {
      count++
      console.log('i', i) //NOTE: If this line is ommited time to find 10,000th prime is 121.157ms
      if (count === nth) {
        console.log('while i', i)
        console.log('count', count)
      }
    }
    i++
  }

}

console.time(logPrimes)

logPrimes(10000)

console.timeEnd(logPrimes) // 2214.486ms

나는 많은 소수를 계산하는 프로그램을 작성하는 데 시간을 보내고 이것이 첫 번째 1.000.000.000 소수를 포함하는 텍스트 파일을 계산하는 데 사용되는 코드입니다. 독일어로되어 있지만 흥미로운 부분은 method calcPrimes() 입니다. 소수는 Primzahlen이라는 배열에 저장됩니다. 계산은 64 비트 정수를 사용하므로 64 비트 CPU를 권장합니다.

import java.io.*;
class Primzahlengenerator {
    long[] Primzahlen;
    int LastUnknown = 2;
    public static void main(String[] args)  {
        Primzahlengenerator Generator = new Primzahlengenerator();
        switch(args.length) {
            case 0:  //Wenn keine Argumente übergeben worden:
                Generator.printHelp(); //Hilfe ausgeben
                return; //Durchfallen verhindern
            case 1:
                try {
                    Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
                }
                catch (NumberFormatException e) {
                    System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
                    Generator.printHelp();                    //Generelle Hilfe ausgeben
                    return;
                }
                break;//dutchfallen verhindern

            case 2:
                switch (args[1]) {
                    case "-l":
                        System.out.println("Sie müsen auch eine Datei angeben!"); //Hilfemitteilung ausgeben
                        Generator.printHelp();                                    //Generelle Hilfe ausgeben
                        return;
                }
                break;//durchfallen verhindern
            case 3:
                try {
                    Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
                }
                catch (NumberFormatException e) {
                    System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
                    Generator.printHelp();                      //Generelle Hilfe ausgeben
                    return;
                }
                switch(args[1]) {
                    case "-l":
                        Generator.loadFromFile(args[2]);//Datei Namens des Inhalts von Argument 3 lesen, falls Argument 2 = "-l" ist
                        break;
                    default:
                        Generator.printHelp();
                        break;
                }
                break;
            default:
                Generator.printHelp();
                return;
        }
        Generator.calcPrims();
    }
    void printHelp() {
        System.out.println("Sie müssen als erstes Argument angeben, die wieviel ersten Primzahlen sie berechnen wollen.");   //Anleitung wie man das Programm mit Argumenten füttern muss
        System.out.println("Als zweites Argument können sie \"-l\" wählen, worauf die Datei, aus der die Primzahlen geladen werden sollen,");
        System.out.println("folgen muss. Sie muss genauso aufgebaut sein, wie eine Datei Primzahlen.txt, die durch den Aufruf \"java Primzahlengenerator 1000 > Primzahlen.txt\" entsteht.");
    }
    void loadFromFile(String File) {
        // System.out.println("Lese Datei namens: \"" + File + "\"");
        try{
            int x = 0;
            BufferedReader in = new BufferedReader(new FileReader(File));
            String line;
            while((line = in.readLine()) != null) {
                Primzahlen[x] = new Long(line).longValue();
                x++;
            }
            LastUnknown = x;
        } catch(FileNotFoundException ex) {
            System.out.println("Die angegebene Datei existiert nicht. Bitte geben sie eine existierende Datei an.");
        } catch(IOException ex) {
            System.err.println(ex);
        } catch(ArrayIndexOutOfBoundsException ex) {
            System.out.println("Die Datei enthält mehr Primzahlen als der reservierte Speicherbereich aufnehmen kann. Bitte geben sie als erstes Argument eine größere Zahl an,");
            System.out.println("damit alle in der Datei enthaltenen Primzahlen aufgenommen werden können.");
            }
        /* for(long prim : Primzahlen) {
            System.out.println("" + prim);
        } */
        //Hier soll code stehen, der von der Datei mit angegebenem Namen ( Wie diese aussieht einfach durch angeben von folgendem in cmd rausfinden:
        //java Primzahlengenerator 1000 > 1000Primzahlen.txt
        //da kommt ne textdatei, die die primzahlen enthält. mit Long.decode(String ziffern).longValue();
        //erhält man das was an der entsprechenden stelle in das array soll. die erste zeile soll in [0] , die zweite zeile in [1] und so weiter.
        //falls im arry der platz aus geht(die exception kenn ich grad nich, aber mach mal:
        //int[] foo = { 1, 2, 3};
        //int bar = foo[4];
        //dann kriegst ne exception, das ist die gleiche die man kriegt, wenn im arry der platzt aus geht.
    }
    void calcPrims() {
        int PrimzahlNummer = LastUnknown;
        // System.out.println("LAstUnknown ist: " + LastUnknown);
        Primzahlen[0] = 2;
        Primzahlen[1] = 3;
        long AktuelleZahl = Primzahlen[PrimzahlNummer - 1];
        boolean IstPrimzahl;
        // System.out.println("2");
        // System.out.println("3");
        int Limit = Primzahlen.length;
        while(PrimzahlNummer < Limit) {
            IstPrimzahl = true;
            double WurzelDerAktuellenZahl = java.lang.Math.sqrt(AktuelleZahl);
            for(int i = 1;i < PrimzahlNummer;i++) {
                if(AktuelleZahl % Primzahlen[i] == 0) {
                    IstPrimzahl = false;
                    break;
                }
                if(Primzahlen[i] > WurzelDerAktuellenZahl) break;
            }
            if(IstPrimzahl) {
                Primzahlen[PrimzahlNummer] = AktuelleZahl;
                PrimzahlNummer++;
                // System.out.println("" + AktuelleZahl);
            }
            AktuelleZahl = AktuelleZahl + 2;
        }
        for(long prim : Primzahlen) {
            System.out.println("" + prim);
        }
    }
}

다음은 내 노트북에서 0.049655 초에 10,000 개의 프라임, 6 초 안에 1,000,000 개의 프라임, 15 초에 처음 2,000,000 개의 프라임을 찾는 코드입니다
. 이 방법은 2 가지 기술을 사용하여 소수를 찾습니다.

  1. 우선 소수 이외의 소수는 소수의 배수의 합성이므로 테스트 코드를 임의의 숫자 대신 작은 소수로 나눠서 테스트합니다. 이는 4 자리 숫자의 경우 10 배 이상 감소합니다. 더 큰 숫자
  2. 두 번째로 소수로 나누는 것 외에도 테스트중인 숫자의 루트보다 작거나 같은 소수로만 나눠 계산을 크게 줄입니다. 이는 숫자의 루트보다 큰 숫자가 대응하는 숫자를 가지기 때문에 작동합니다 우리는 이미 루트보다 작은 모든 숫자를 테스트했기 때문에 테스트중인 숫자의 루트보다 큰 숫자를 신경 쓸 필요가 없습니다.

처음 10,000 개의 소수에 대한 샘플 출력
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk

다음은 C 언어의 코드입니다. 1을 입력 한 다음 10,000을 입력하여 처음 10,000 개의 소수를 인쇄하십시오.
편집 : 나는 이것이 수학 라이브러리를 포함하는 것을 잊었다. 만약 당신이 Windows 또는 Visual Studio에 있다면 그보다 좋을 것이지만 리눅스에서는 -lm 인수를 사용하여 코드를 컴파일해야하거나 코드가 작동하지 않을 수있다
예 : gcc -Wall -o "% e ""% f "-lm

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

/* Finding prime numbers */
int main()
{   
    //pre-phase
    char d,w;
    int l,o;
    printf("  1. Find first n number of prime numbers or Find all prime numbers smaller than n ?\n"); // this question helps in setting the limits on m or n value i.e l or o 
    printf("     Enter 1 or 2 to get anwser of first or second question\n");
    // decision making
    do
    {
        printf("  -->");
        scanf("%c",&d);
        while ((w=getchar()) != '\n' && w != EOF);
        if ( d == '1')
        {
            printf("\n  2. Enter the target no. of primes you will like to find from 3 to 2,000,000 range\n  -->");
            scanf("%10d",&l);
            o=INT_MAX;
            printf("  Here we go!\n\n");
            break;
        }
        else if ( d == '2' )
        {
            printf("\n  2.Enter the limit under which to find prime numbers from 5 to 2,000,000 range\n  -->");
            scanf("%10d",&o);
            l=o/log(o)*1.25;
            printf("  Here we go!\n\n");
            break;
        }
        else printf("\n  Try again\n");
    }while ( d != '1' || d != '2' );

    clock_t start, end;
    double cpu_time_used;
    start = clock(); /* starting the clock for time keeping */

    // main program starts here
    int i,j,c,m,n; /* i ,j , c and m are all prime array 'p' variables and n is the number that is being tested */
    int s,x;

    int p[ l ]; /* p is the array for storing prime numbers and l sets the array size, l was initialized in pre-phase */
    p[1]=2;
    p[2]=3;
    p[3]=5;
    printf("%10dst:%10d\n%10dnd:%10d\n%10drd:%10d\n",1,p[1],2,p[2],3,p[3]); // first three prime are set
    for ( i=4;i<=l;++i ) /* this loop sets all the prime numbers greater than 5 in the p array to 0 */
        p[i]=0;

    n=6; /* prime number testing begins with number 6 but this can lowered if you wish but you must remember to update other variables too */
    s=sqrt(n); /* 's' does two things it stores the root value so that program does not have to calaculate it again and again and also it stores it in integer form instead of float*/
    x=2; /* 'x' is the biggest prime number that is smaller or equal to root of the number 'n' being tested */

    /* j ,x and c are related in this way, p[j] <= prime number x <= p[c] */

    // the main loop begins here
    for ( m=4,j=1,c=2; m<=l && n <= o;)
    /* this condition checks if all the first 'l' numbers of primes are found or n does not exceed the set limit o */
    {
            // this will divide n by prime number in p[j] and tries to rule out non-primes
            if ( n%p[j]==0 )
            {
                /* these steps execute if the number n is found to be non-prime */

                ++n; /* this increases n by 1 and therefore sets the next number 'n' to be tested */
                s=sqrt(n); /* this calaulates and stores in 's' the new root of number 'n' */
                if ( p[c] <= s && p[c] != x ) /* 'The Magic Setting' tests the next prime number candidate p[c] and if passed it updates the prime number x */
                {
                    x=p[c];
                    ++c;
                }
                j=1;
                /* these steps sets the next number n to be tested and finds the next prime number x if possible for the new number 'n' and also resets j to 1 for the new cycle */
                continue; /* and this restarts the loop for the new cycle */
            }
            // confirmation test for the prime number candidate n
            else if ( n%p[j]!=0 && p[j]==x )
            {
                /* these steps execute if the number is found to be prime */
                p[m]=n;
                printf("%10dth:%10d\n",m,p[m]);
                ++n;
                s = sqrt(n);
                ++m;
                j=1;
                /* these steps stores and prints the new prime number and moves the 'm' counter up and also sets the next number n to be tested and also resets j to 1 for the new cycle */
                continue; /* and this restarts the loop */
                /* the next number which will be a even and non-prime will trigger the magic setting in the next cycle and therfore we do not have to add another magic setting here*/
            }
            ++j; /* increases p[j] to next prime number in the array for the next cycle testing of the number 'n' */
            // if the cycle reaches this point that means the number 'n' was neither divisible by p[j] nor was it a prime number
            // and therfore it will test the same number 'n' again in the next cycle with a bigger prime number
    }
    // the loops ends
    printf("  All done !!\n");
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("  Time taken : %lf sec\n",cpu_time_used);
}

몇 가지 팁을 줄 수 있습니다. 구현해야합니다.

  1. 각 숫자마다 그 숫자의 절반을 얻으십시오. 예를 들어 21을 확인하기 위해 나머지를 2-10 범위로 나눠서 얻는다.
  2. 홀수 인 경우 홀수로만 나누고 그 반대의 경우도 마찬가지입니다. 21과 같이 3, 5, 7, 9로만 나눕니다.

내가 지금까지 가장 효율적인 방법.


복잡한 알고리즘을 코딩하는 대신 처음 10000 소수만 원하므로 다음을 제안합니다.

boolean isPrime(int n){
//even but is prime
    if(n==2)
        return true;
//even numbers filtered already 
    if(n==0 || n==1 || n%2==0)
        return false;

// loop for checking only odd factors
// i*i <= n  (same as i<=sqrt(n), avoiding floating point calculations)
    for(int i=3 ; i*i <=n ; i+=2){
    // if any odd factor divides n then its not a prime!
        if(n%i==0)
            return false;
    }
// its prime now
    return true;
}

이제 전화가 필요합니다

for(int i=1 ; i<=1000 ; i++){
    if(isPrime(i)){
       //do something
    }
}

에라토스테네스의 체 (Sieve of Eratosthenes)를 사용하면 "알려진 전체"소수 알고리즘에 비해 계산이 훨씬 빠릅니다.

Wiki ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ) 의 의사 코드를 사용 하면 C #에 대한 솔루션을 가질 수 있습니다.

/// Get non-negative prime numbers until n using Sieve of Eratosthenes.
public int[] GetPrimes(int n) {
    if (n <= 1) {
        return new int[] { };
    }

    var mark = new bool[n];
    for(var i = 2; i < n; i++) {
        mark[i] = true;
    }

    for (var i = 2; i < Math.Sqrt(n); i++) {
        if (mark[i]) {
            for (var j = (i * i); j < n; j += i) {
                mark[j] = false;
            }
        }
    }

    var primes = new List<int>();
    for(var i = 3; i < n; i++) {
        if (mark[i]) {
            primes.Add(i);
        }
    }

    return primes.ToArray();
}

GetPrimes (100000000)는 2 초와 330ms가 걸립니다.

참고 : 값은 하드웨어 사양에 따라 다를 수 있습니다.


이것은 오래된 질문이지만, 여기에 모두가 빠진 것이 있습니다 ...

소수를 위해이 작은, 재판 부문은 아닌 것을 ... 25 시험에 이렇게 몇몇 소수와 100에서 소수, 이러한 작은 소수가 느린있다, 우리는 깔끔한 트릭을 당겨 수 있습니다!

a가 b에 대한 코 프라임이면 gcd ab = 1입니다. 재미있는 단어. 주요 요소를 공유하지 않음을 의미합니다 . 따라서 우리는 한 번의 GCD 호출로 몇 가지 소수에 의한 분할 성을 테스트 할 수 있습니다. 얼마나? 처음 15 개의 소수의 곱은 2 ^ 64보다 작습니다. 그리고 다음 10 개의 제품도 2 ^ 64보다 작습니다. 우리 모두 필요한 25 가지입니다. 그러나 그만한 가치가 있습니까?

보자 :

check x = null $ filter ((==0) . (x `mod`)) $ [<primes up to 101>]
Prelude> length $ filter check [101,103..85600]
>>> 9975
(0.30 secs, 125,865,152 bytes

a = 16294579238595022365 :: Word64
b = 14290787196698157718
pre = [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]
primes = (pre ++) $ filter ((==1) . gcd a) $ filter ((==1) . gcd b) [99,101..85600]
main = print $ length primes

Prelude> main
>>> 10000
(0.05 secs, 36,387,520 bytes)

6 배 개선.

( length 계산되는리스트를 강제한다. 기본적으로 하스켈 1 개 유니 코드 문자 한번에 물건을 출력하고 있으므로, 실제로 인쇄하는 것 중 지배 사용 시간이나 실제 코드의 양을 지배 목록).

물론 이것은 오래된 랩톱에서 GHCi (통역 코드를 실행하는 repl)에서 실행 중이며이 숫자를 int64 s 또는 BigInt s 로 해석하지 않으며 요청해도 (그렇지 않으면 강제 할 없습니다) , 그러나 그것은 추악하고 실제로 도움이되지 않습니다). 그것은 사전 조회를 통해 특정 유형에 특화 될 수있는 일반화 된 정수와 같은 것으로 모든 단일 숫자를 해석 하고 링크 된 목록 (여기서 컴파일되지 않았으므로 융합되지 않음)을 3 번 통과합니다. 흥미롭게도 두 필터를 수동으로 융합하면 실제로 REPL에서 속도가 느려집니다.

그것을 컴파일하자 :

...\Haskell\8.6\Testbed>Primes.exe +RTS -s
10000
606,280 bytes allocated in the heap
Total   time    0.000s  (  0.004s elapsed)

Windows 때문에 RTS 보고서를 사용합니다. 일부 라인은 관련이 없기 때문에 다듬어졌습니다. 다른 GC 데이터 또는 실행의 일부만 측정 한 것이기 때문에 함께 0.004 초 이하로 줄었습니다. Haskell은 실제로 그 중 많은 것을 수행하지 않기 때문에 지속적인 접는 것은 아닙니다. 우리가 끊임없이 자신을 접 으면 ( main = print 10000 ) 할당량이 크게 줄어 듭니다.

...Haskell\8.6\Testbed>Primes.exe +RTS -s
10000
47,688 bytes allocated in the heap
Total   time    0.000s  (  0.001s elapsed)

말 그대로 런타임을로드하기에 충분하면 숫자를 인쇄하고 종료하는 것 외에는 할 일이 없다는 것을 발견하십시오. 휠 인수 분해를 추가합시다 :

wheel = scanl (+) 7 $ cycle [4, 2, 4, 2, 4, 6, 2, 6]
primes = (pre ++) $ filter ((==1) . gcd a) $ filter ((==1) . gcd b) $ takeWhile (<85600) wheel

Total   time    0.000s  (  0.003s elapsed)

에 대한 참조를 기준으로 약 1/3을 줄이지 main = print 10000 만 더 많은 최적화를위한 여지가 분명히 있습니다. 예를 들어 실제로는 GC 수행을 중단했지만 조정하면 힙 사용이 없어야합니다. 어떤 이유로 든 프로파일 링을 위해 컴파일하면 실제로 런타임이 2 밀리 초로 줄어 듭니다.

Tue Nov 12 21:13 2019 Time and Allocation Profiling Report  (Final)

   Primes.exe +RTS -p -RTS

total time  =        0.00 secs   (2 ticks @ 1000 us, 1 processor)
total alloc =     967,120 bytes  (excludes profiling overheads)

나는 이것을 그대로 두겠습니다. 랜덤 지터가 지배하기 시작합니다.


@ 매트 : log (log (10000)) ~ 2

Atkin의 체 (sieve ) : 위키피디아 기사에서 인용했습니다.

이 체는 N 1 / 2 + o (1) 비트의 메모리 만있는 O(N/log log N) 연산을 사용하여 최대 N까지 소수를 계산합니다. 이는 O(N) 연산과 O (N 1/2 (log log N) / log N) 비트 메모리를 사용하는 Eratosthenes의 체보다 약간 낫습니다 (AOL Atkin, DJ Bernstein, 2004) . 이러한 점근 적 계산 복잡도에는 휠 분해와 같은 간단한 최적화 및 계산을 더 작은 블록으로 나누는 것이 포함됩니다.

O(N) (Eratosthenes의 경우) 및 O(N/log(log(N))) (Atkin의 경우)에 따라 점근 적 계산 복잡성이 주어지면 구현 된 알고리즘이 더 빠를 것이라고 말할 수 없습니다 (작은 N=10_000 ).

Achim Flammenkamp는 Eratosthenes의 체 에서 다음 과 같이 썼습니다.

인용 :

@ num1

약 10 ^ 9보다 큰 구간의 경우, 확실히 10 ^ 10보다 큰 구간의 경우, 에라토스테네스 시브 (Sieve of Eratosthenes)는 복구 할 수없는 이차 2 차 형태를 사용하는 Atkins와 Bernstein 시브보다 성능이 뛰어납니다. 배경 정보와 W. Galway의 Ph.D. 단락 5에 대해서는 논문을 참조하십시오. 명제.

따라서 10_000 의 에라토스테네스 체는 Atkin의 체보다 빠를 수 있습니다.

OP에 응답하기 위해 코드는 prime_sieve.c ( num1 인용)


나는 Eratosthenes의 체 또는 Atkin의 체인 체를 추천합니다 .

체 또는 에라토스테네스는 아마도 소수 목록을 찾는 가장 직관적 인 방법 일 것입니다. 기본적으로 당신은 :

  1. 숫자 목록을 2에서 원하는 한도까지 적습니다. 1000이라고합시다.
  2. 교차하지 않는 첫 번째 숫자 (첫 번째 반복의 경우 2 임)를 가져 와서 해당 숫자의 모든 배수를 목록에서 제거하십시오.
  3. 목록의 끝에 도달 할 때까지 2 단계를 반복하십시오. 교차하지 않은 모든 숫자는 소수입니다.

분명히이 알고리즘을 더 빠르게 작동시키기 위해 수행 할 수있는 최적화가 꽤 있지만 기본 아이디어입니다.

Atkin의 체는 비슷한 접근법을 사용하지만 불행히도 나는 그것을 당신에게 설명하기에 충분하지 않습니다. 그러나 고대의 펜티엄 II-350에서 연결된 모든 알고리즘을 1000000000까지 알아내는 데 8 초가 걸린다는 것을 알고 있습니다.

에라토스테네스의 체 소스 코드 : http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/

Atkin의 체 소스 코드 : http://cr.yp.to/primegen.html


다음 Mathcad 코드는 3 분 이내에 첫 번째 백만 소수를 계산했습니다.

이것은 모든 숫자에 대해 부동 소수점을 두 배로 사용하며 기본적으로 해석됩니다. 구문이 명확하기를 바랍니다.


다음은 내가 며칠 전에 PowerShell에서 작성한 Eratosthenes의 체입니다. 리턴해야하는 소수의 수를 식별하는 매개 변수가 있습니다.

#
# generate a list of primes up to a specific target using a sieve of eratosthenes
#
function getPrimes { #sieve of eratosthenes, http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    param ($target,$count = 0)
    $sieveBound = [math]::ceiling(( $target - 1 ) / 2) #not storing evens so count is lower than $target
    $sieve = @($false) * $sieveBound
    $crossLimit = [math]::ceiling(( [math]::sqrt($target) - 1 ) / 2)
    for ($i = 1; $i -le $crossLimit; $i ++) {
        if ($sieve[$i] -eq $false) {
            $prime = 2 * $i + 1
            write-debug "Found: $prime"
            for ($x = 2 * $i * ( $i + 1 ); $x -lt $sieveBound; $x += 2 * $i + 1) {
                $sieve[$x] = $true
            }
        }
    }
    $primes = @(2)
    for ($i = 1; $i -le $sieveBound; $i ++) {
        if($count -gt 0 -and $primes.length -ge $count) {
            break;
        }
        if($sieve[$i] -eq $false) {
            $prime = 2 * $i + 1
            write-debug "Output: $prime"
            $primes += $prime
        }
    }
    return $primes
}

여기 내 VB 2008 코드가 있습니다.이 코드는 내 업무용 랩톱에서 1 분 27 초 내에 <10,000,000 미만의 모든 소수를 찾습니다. 짝수를 건너 뛰고 테스트 번호의 sqrt 인 소수만 찾습니다. 0에서 센티미터 값까지 소수를 찾도록 설계되었습니다.

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles 
Button1.Click

    Dim TestNum As Integer
    Dim X As Integer
    Dim Z As Integer
    Dim TM As Single
    Dim TS As Single
    Dim TMS As Single
    Dim UnPrime As Boolean
    Dim Sentinal As Integer
    Button1.Text = "Thinking"
    Button1.Refresh()
    Sentinal = Val(SentinalTxt.Text)
    UnPrime = True
    Primes(0) = 2
    Primes(1) = 3
    Z = 1
    TM = TimeOfDay.Minute
    TS = TimeOfDay.Second
    TMS = TimeOfDay.Millisecond
    For TestNum = 5 To Sentinal Step 2
        Do While Primes(X) <> 0 And UnPrime And Primes(X) ^ 2 <= TestNum
            If Int(TestNum / Primes(X)) - (TestNum / Primes(X)) = 0 Then
                UnPrime = False
            End If
            X = X + 1

        Loop
        If UnPrime = True Then
            X = X + 1
            Z = Z + 1
            Primes(Z) = TestNum
        End If
        UnPrime = True
        X = 0
    Next
    Button1.Text = "Finished with " & Z
    TM = TimeOfDay.Minute - TM
    TS = TimeOfDay.Second - TS
    TMS = TimeOfDay.Millisecond - TMS
    ShowTime.Text = TM & ":" & TS & ":" & TMS
End Sub

전혀 효율적이지 않지만 정규 표현식을 사용하여 소수를 테스트 할 수 있습니다.

/^1?$|^(11+?)\1+$/

이는 k " 1 "로 구성된 문자열의 경우 k 소수 가 아닌지 여부를 테스트합니다 (즉, 문자열이 하나의 " 1 "로 구성되는지 또는 n- ary 곱으로 표현할 수있는 " 1 "로 구성되는지).


체가 잘못된 답인 것 같습니다. 체는 첫 번째 N 소수가 아닌 숫자 N 까지 소수를 제공합니다. @Imran 또는 @Andrew Szeto를 실행하면 소수를 N까지 얻을 수 있습니다.

결과 크기의 특정 크기에 도달하고 이미 얻은 숫자 캐싱을 사용할 때까지 점점 더 큰 숫자의 체를 계속 시도하면 체를 계속 사용할 수 있지만 @ Pat 's와 같은 솔루션보다 여전히 빠르지 않다고 생각합니다. .


하스켈에서, 우리는 에라토스테네스의 체에 대한 수학적 정의를 거의 단어로 적을 수 있습니다. " 소수는 임의의 숫자가없는 1 이상의 자연수입니다. 여기서 각 소수의 배수로 열거 된 복합물은 ":

import Data.List.Ordered (minus, union)

primes = 2 : minus [3..] (foldr (\p r -> p*p : union [p*p+p, p*p+2*p..] r)
                                [] primes)

primes !! 10000 primes !! 10000 은 거의 즉각적입니다.

참고 문헌 :

위의 코드는 확률에 대해서만 작업하도록 쉽게 조정됩니다. primes = 2 : 3 : minus [5,7..] (foldr (\pr -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)) . 트리와 같은 구조로 접음으로써 시간 복잡성이 훨씬 향상되고 (최적의 로그 요소까지), 다단계 프라임 생산 으로 공간 복잡성이 크게 개선 됩니다.

primes = 2 : _Y ( (3:) . sieve 5 . _U . map (\p -> [p*p, p*p+2*p..]) )
  where
    _Y g = g (_Y g)                        -- non-sharing fixpoint combinator
    _U ((x:xs):t) = x : (union xs . _U . pairs) t       -- ~= nub.sort.concat
    pairs    (xs:ys:t)  = union xs ys : pairs t
    sieve k s@(x:xs) | k < x      = k : sieve (k+2) s   -- ~= [k,k+2..]\\s,
                     | otherwise  =     sieve (k+2) xs  --   when s⊂[k,k+2..]

(하스켈에서 괄호는 그룹화에 사용되며, 함수 호출은 병치로만 표시되며, (:) 는 목록에 대한 cons 연산자이며, (.) 는 기능 구성 연산자입니다. (f . g) x = (\y -> f (gy)) x = f (gx) ).


BenGoldberg 가 언급 한 deque sieve 알고리즘 은 매우 우아 할뿐만 아니라 때로는 실용적으로 유용 할 수 있기 때문에 면밀히 살펴볼 가치가 있습니다 (순수하게 학술적인 운동 인 Atkin의 체와는 달리).

deque sieve 알고리즘의 기본 아이디어는 현재 '활성'인 각 요소 (즉, 제곱이 가장 낮은 수를 초과하지 않는 소수)에 대해 하나 이상의 개별 배수를 포함하기에 충분히 큰 작은 슬라이딩 체를 사용하는 것입니다. 현재 움직이는 체로 표현됩니다. SoE와의 또 다른 차이점은 deque sieve가 실제 요소를 부울이 아닌 복합 슬롯에 저장한다는 것입니다.

이 알고리즘은 필요에 따라 체의 크기를 확장하여 체가 CPU의 L1 캐시 용량을 상당히 초과 할 때까지 광범위한 범위에서 성능을 상당히 균일하게합니다. 완전히 맞는 마지막 소수는 25,237,523 (1,579,791 번째 소수)이며 알고리즘의 합리적인 작동 범위에 대한 대략적인 수치를 제공합니다.

이 알고리즘은 상당히 단순하고 강력하며 분류되지 않은 에라토스테네스 (Eratosthenes) 체보다 훨씬 넓은 범위의 성능을 제공합니다. 후자는 그것의 체가 캐시에 완전히 들어 맞는 한, 즉 바이트 크기의 부울을 가진 홀수 전용 체의 경우 2 ^ 16까지 훨씬 빠릅니다. 핸디캡에도 불구하고 (적어도 C / C ++, Pascal 또는 Java / C #와 같은 컴파일 된 언어에서는) 항상 deque보다 훨씬 빠르지 만 성능은 점점 더 떨어집니다.

C #에서 deque sieve 알고리즘의 렌더링은 많은 결함에도 불구하고 언어가 매우 번거롭고 실용적인 C ++보다 알고리즘 및 실험에 훨씬 더 실용적이라는 것을 알기 때문에 C #에서 deque sieve 알고리즘의 렌더링입니다. (Sidenote : 무료 LINQPad 를 사용하여 프로젝트, makefile, 디렉토리 등을 설정하는 데 지장을주지 않고 바로 뛰어들 수 있으며, 파이썬 프롬프트와 같은 수준의 상호 작용을 제공합니다).

C #에는 명시 적 deque 유형이 없지만 일반 List<int> 는 알고리즘을 보여주기에 충분합니다.

참고 :이 버전은 프라임에 deque를 사용하지 않습니다. 단순히 n 프라임에서 sqrt (n)을 팝하는 것은 의미가 없기 때문입니다. 100 개의 소수를 제거하고 9900을 떠나는 것이 얼마나 좋을까요? 적어도 이런 식으로 모든 프라임은 깔끔한 벡터로 수집되어 추가 처리 준비가 완료됩니다.

static List<int> deque_sieve (int n = 10000)
{
    Trace.Assert(n >= 3);

    var primes = new List<int>()  {  2, 3  };
    var sieve = new List<int>()  {  0, 0, 0  };

    for (int sieve_base = 5, current_prime_index = 1, current_prime_squared = 9; ; )
    {
        int base_factor = sieve[0];

        if (base_factor != 0)
        {
            // the sieve base has a non-trivial factor - put that factor back into circulation
            mark_next_unmarked_multiple(sieve, base_factor);
        }
        else if (sieve_base < current_prime_squared)  // no non-trivial factor -> found a non-composite
        {
            primes.Add(sieve_base);

            if (primes.Count == n)
                return primes;
        }
        else // sieve_base == current_prime_squared
        {
            // bring the current prime into circulation by injecting it into the sieve ...
            mark_next_unmarked_multiple(sieve, primes[current_prime_index]);

            // ... and elect a new current prime
            current_prime_squared = square(primes[++current_prime_index]);
        }

        // slide the sieve one step forward
        sieve.RemoveAt(0);  sieve_base += 2;
    }
}

다음은 두 가지 도우미 기능입니다.

static void mark_next_unmarked_multiple (List<int> sieve, int prime)
{
    int i = prime, e = sieve.Count;

    while (i < e && sieve[i] != 0)
        i += prime;

    for ( ; e <= i; ++e)  // no List<>.Resize()...
        sieve.Add(0);

    sieve[i] = prime;
}

static int square (int n)
{
    return n * n;
}

아마도 알고리즘을 이해하는 가장 쉬운 방법은 알고리즘이 세그먼트 크기가 1 인 특수 세그먼트 화 된 에라토스테네스 (Eratosthenes)의 체로 분류되는 것으로 상상할 수 있습니다. 세그먼트의 단일 셀 (일명 sieve[0] )은 오버 플로우 영역의 일부인 동안 오버런 되었기 때문에 이미 도달했을 때 이미 체질되었습니다.

sieve_front 또는 window_base 는 Ben의 코드 또는 세그먼트 / 윈도우 체의 구현과 평행을 sieve_front 수있는 좋은 이름이지만 sieve[0] 표시되는 숫자는 sieve_base 유지됩니다.

sieve[0]sieve[0] 이 아닌 값이 포함 된 경우 해당 값은 sieve_base 의 인수이므로 복합으로 인식 할 수 있습니다. 셀 0은 해당 계수의 배수이므로 다음 홉을 계산하기가 쉽습니다. 이는 단순히 0에 해당 계수를 더한 것입니다. 그 세포가 다른 인자에 의해 이미 점유되어 있다면, 우리는 다른 인자가 현재 주차되어 있지 않은 인자의 배수를 찾을 때까지 단순히 인자를 다시 추가합니다 (필요한 경우 체 확장). 이것은 또한 정상 세그먼트 화 된 체에서와 같이 한 세그먼트에서 다음 세그먼트로 다양한 프라임의 현재 작업 오프셋을 저장할 필요가 없음을 의미합니다. sieve[0] 에서 계수를 찾을 때마다 현재 작업 오프셋은 0입니다.

현재 프라임은 다음과 같은 방식으로 작동합니다. 프라임은 스트림에서 자체 발생 후에 만 ​​전류가 될 수 있으며 (즉, 인자로 표시되지 않았기 때문에 프라임으로 감지 된 경우) sieve[0] 이 정사각형에 도달 할 때까지 전류를 유지합니다. 이 소수의 모든 낮은 배수는 일반적인 SoE 에서처럼 작은 소수의 활동으로 인해 잘려 나갔을 것입니다. 그러나 정사각형의 유일한 요소는 프라임 그 자체이며 아직이 시점에서 유통되지 않기 때문에 더 작은 소수는 그 어느 것도 광장에서 나올 수 없습니다. sieve_base == current_prime_squared ( sieve_base == current_prime_squared sieve[0] == 0 을 의미)의 경우 알고리즘이 취한 조치를 설명합니다.

이제 sieve[0] == 0 && sieve_base < current_prime_squared 를 쉽게 설명 할 수 있습니다. 이는 sieve_base 가 현재 소수보다 작은 소수의 배수 일 수 없거나 복합으로 표시 될 수 있음을 의미합니다. 현재 프라임의 제곱보다 값이 작기 때문에 현재 프라임의 배수가 더 높을 수 없습니다. 따라서 새로운 프라임이어야합니다.

이 알고리즘은 명백히 에라토스테네스의 체에서 영감을 얻었지만 분명히 분명히 다릅니다. 에라토스테네스 시브 (Eeve of Eratosthenes)는 기본 작업의 단순성에서 뛰어난 속도를 얻습니다. 작업의 각 단계마다 하나의 단일 인덱스 추가 및 하나의 저장소가 오랜 시간 동안 수행되는 모든 것입니다.

다음은 일반적으로 Ushort 범위, 즉 2 ^ 16까지 인자 소수를 체질하는 데 사용하는 간단하고 분할되지 않은 Eratosthenes 체입니다. 이 게시물에서는 intushort 로 대체하여 2 ^ 16 이상으로 작동하도록 수정했습니다.

static List<int> small_odd_primes_up_to (int n)
{
    var result = new List<int>();

    if (n < 3)
        return result;

    int sqrt_n_halved = (int)(Math.Sqrt(n) - 1) >> 1, max_bit = (n - 1) >> 1;
    var odd_composite = new bool[max_bit + 1];

    for (int i = 3 >> 1; i <= sqrt_n_halved; ++i)
        if (!odd_composite[i])
            for (int p = (i << 1) + 1, j = p * p >> 1; j <= max_bit; j += p)
                odd_composite[j] = true;

    result.Add(3);  // needs to be handled separately because of the mod 3 wheel

    // read out the sieved primes
    for (int i = 5 >> 1, d = 1; i <= max_bit; i += d, d ^= 3)
        if (!odd_composite[i])
            result.Add((i << 1) + 1);

    return result;
}

첫 10000 프라임을 체질하면 32KB의 일반적인 L1 캐시는 초과되지만이 기능은 여전히 ​​매우 빠릅니다 (C #에서도 밀리 초의 비율).

이 코드를 deque sieve와 비교하면 deque sieve의 작업이 훨씬 더 복잡하다는 것을 쉽게 알 수 있으며 항상 행에서 가장 짧은 교차 스트레칭을 수행하기 때문에 오버 헤드를 효과적으로 상각 할 수 없습니다. (이미 교차 된 모든 배수를 건너 뛴 후 정확히 하나의 단일 교차).

참고 : C # 코드는 uint 대신 int 를 사용합니다. 새로운 컴파일러는 아마도 사람들을 부호있는 정수로 밀기 위해 uint 에 대한 하위 표준 코드를 생성하는 습관을 가지고 있기 때문입니다 ... 위의 코드의 C ++ 버전에서는 자연스럽게 unsigned 것을 사용했습니다. 벤치 마크는 아마도 적절한 deque 유형 ( std::deque<unsigned> ; unsigned short 사용으로 인한 성능 향상이 없음)을 기반으로하기를 원했기 때문에 C ++에 있어야했습니다. 내 Haswell 랩탑 번호 (VC ++ 2015 / x64)는 다음과 같습니다.

deque vs simple: 1.802 ms vs 0.182 ms
deque vs simple: 1.836 ms vs 0.170 ms 
deque vs simple: 1.729 ms vs 0.173 ms

참고 : C # 시간은 C ++ 타이밍의 거의 두 배가되며 C #에는 꽤 적합하며 ìt는 Deque로 남용 되더라도 List<int> 가 엉터리가 아님을 보여줍니다.

간단한 시브 (sieve) 코드는 이미 정상적인 작업 범위 (L1 캐시 크기가 50 % 초과, 교환 원 캐시 스 래싱)를 초과하여 작동하더라도 물에서 디크를 날려 버립니다. 여기서 지배적 인 부분은 체질 된 프라임을 읽는 것이므로 캐시 문제의 영향을 많이받지 않습니다. 어쨌든이 기능은 요인의 요인, 즉 3 수준 시브 (sieve) 계층의 수준 0을 체질하기 위해 설계되었으며 일반적으로 단지 수백 개의 요인 또는 적은 수의 요인 만 반환해야합니다. 따라서 단순성.

세그먼트 화 된 체를 사용하고 체질 된 소수를 추출하기위한 코드를 최적화함으로써 (단계 3 모드 및 2 회 언 롤링, 또는 모드 15 및 1 회 언 롤링) 성능을 한 단계 이상 향상시킬 수 있지만, 더 많은 성능을 압박 할 수 있습니다. 모든 트리밍과 함께 mod 16 또는 mod 30 휠을 사용하여 코드를 작성합니다 (즉, 모든 잔류 물을 완전히 풀기). 비슷한 문제가 논의 된 코드 검토에서 소수 찾아 소수에 대한 대답에 설명되어 있습니다. 그러나 일회성 작업을 위해 밀리 초 미만의 시간을 개선한다는 점을 이해하기는 어렵습니다 ...

상황을 조금만 살펴보면 최대 100,000,000을 체질하는 C ++ 타이밍이 있습니다.

deque vs simple: 1895.521 ms vs 432.763 ms
deque vs simple: 1847.594 ms vs 429.766 ms
deque vs simple: 1859.462 ms vs 430.625 ms

대조적으로, 벨과 휘파람이 적은 C #의 세그먼트 체는 95ms에서 동일한 작업을 수행합니다 (현재 C #에서만 코드 도전을하기 때문에 C ++ 타이밍을 사용할 수 없음).

파이썬과 같은 해석 언어에서는 모든 작업에 비용이 많이 들고 예측 된 분기 또는 잘못 예측 된 분기 또는 하위 사이클 연산 (시프트, 추가) 및 다중 사이클 연산 (곱셈)으로 인해 해석기 오버 헤드가 모든 차이를 감소시키는 해석 언어에서는 상황이 결정적으로 다르게 보일 수 있습니다. , 그리고 아마도 분열). 그것은 에라토스테네스 시브 (Eeve of Eratosthenes)의 단순성 이점을 약화시켜야 할 의무가 있으며, 이는 디크 솔루션을 좀 더 매력적으로 만들 수 있습니다.

또한이 주제의 다른 응답자가보고 한 많은 타이밍은 아마도 출력 시간에 의해 좌우 될 것입니다. 그것은 완전히 다른 전쟁이며, 내 주요 무기는 다음과 같은 간단한 클래스입니다.

class CCWriter
{
    const int SPACE_RESERVE = 11;  // UInt31 + '\n'

    public static System.IO.Stream BaseStream;
    static byte[] m_buffer = new byte[1 << 16];  // need 55k..60k for a maximum-size range
    static int m_write_pos = 0;
    public static long BytesWritten = 0;         // for statistics

    internal static ushort[] m_double_digit_lookup = create_double_digit_lookup();

    internal static ushort[] create_double_digit_lookup ()
    {
        var lookup = new ushort[100];

        for (int lo = 0; lo < 10; ++lo)
            for (int hi = 0; hi < 10; ++hi)
                lookup[hi * 10 + lo] = (ushort)(0x3030 + (hi << 8) + lo);

        return lookup;
    }

    public static void Flush ()
    {
        if (BaseStream != null && m_write_pos > 0)
            BaseStream.Write(m_buffer, 0, m_write_pos);

        BytesWritten += m_write_pos;
        m_write_pos = 0;
    }

    public static void WriteLine ()
    {
        if (m_buffer.Length - m_write_pos < 1)
            Flush();

        m_buffer[m_write_pos++] = (byte)'\n';
    }

    public static void WriteLinesSorted (int[] values, int count)
    {
        int digits = 1, max_value = 9;

        for (int i = 0; i < count; ++i)
        {
            int x = values[i];

            if (m_buffer.Length - m_write_pos < SPACE_RESERVE)
                Flush();

            while (x > max_value)
                if (++digits < 10)
                    max_value = max_value * 10 + 9;
                else
                    max_value = int.MaxValue;               

            int n = x, p = m_write_pos + digits, e = p + 1;

            m_buffer[p] = (byte)'\n';

            while (n >= 10)
            {
                int q = n / 100, w = m_double_digit_lookup[n - q * 100];
                n = q;
                m_buffer[--p] = (byte)w;
                m_buffer[--p] = (byte)(w >> 8);
            }

            if (n != 0 || x == 0)
                m_buffer[--p] = (byte)((byte)'0' + n);

            m_write_pos = e;
        }
    }
}

10000 (정렬 된) 숫자를 쓰는 데 1ms 미만이 소요됩니다. 최소한의 번거롭고 오버 헤드가없는 코딩 과제 제출에 텍스트를 포함하기위한 정적 클래스입니다.

일반적으로 집중식 작업이 전체 배치에서 수행되면 특정 범위를 체질 한 다음 모든 소수를 벡터 / 배열로 추출 한 다음 전체 배열을 블라스트 한 다음 다음 범위를 체질하는 것이 훨씬 빠릅니다. 모든 것을 하나로 모으는 대신. 특정 작업에 초점을 맞춘 별도의 기능을 사용하면 혼합 및 매칭이 쉬워지고 재사용이 가능하며 개발 / 테스트가 쉬워집니다.


GateKiller 에서 적응하고 계속 사용하는 마지막 버전은 다음과 같습니다.

    public IEnumerable<long> PrimeNumbers(long number)
    {
        List<long> primes = new List<long>();
        for (int i = 2; primes.Count < number; i++)
        {
            bool divisible = false;

            foreach (int num in primes)
            {
                if (i % num == 0)
                    divisible = true;

                if (num > Math.Sqrt(i))
                    break;
            }

            if (divisible == false)
                primes.Add(i);
        }
        return primes;
    }

기본적으로 동일하지만 "sqrt에서 중단"제안을 추가하고 주변 변수를 변경하여 나에게 더 적합하도록 만들었습니다. (나는 오일러에서 일하고 있었고 10001 프라임이 필요했습니다)


Atkin의 체 는 아마도 당신이 찾고있는 것일 것입니다. 상한 실행 시간은 O (N / log log N)입니다.

6의 배수보다 1을 1 이상 더 적은 수로 만 실행하면 3보다 큰 모든 소수가 6의 배수에서 1만큼 떨어져 있으므로 훨씬 빠를 수 있습니다. 나의 진술을위한 자료


CodeProject 에서 찾은 코드를 다음과 같이 만들었습니다.

ArrayList primeNumbers = new ArrayList();

for(int i = 2; primeNumbers.Count < 10000; i++) {
    bool divisible = false;

    foreach(int number in primeNumbers) {
        if(i % number == 0) {
            divisible = true;
        }
    }

    if(divisible == false) {
        primeNumbers.Add(i);
        Console.Write(i + " ");
    }
}

내 ASP.NET 서버에서 이것을 테스트하는 데 약 1 분이 소요되었습니다.


using System;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            int n, i = 3, j, c;
            Console.WriteLine("Please enter your integer: ");
            n = Convert.ToInt32(Console.ReadLine());
            if (n >= 1)
            {
                Console.WriteLine("First " + n + " Prime Numbers are");
                Console.WriteLine("2");
            }
            for(j=2;j<=n;)
            {
                for(c=2;c<=i-1;c++)
                {
                    if(i%c==0)
                        break;
                }
                    if(c==i)
                    {
                        Console.WriteLine(i);
                        j++;
                    }
                    i++;                                
            }
            Console.Read();
        }
    }
}




primes