Überprüfen Sie, ob Nummer während der Kompilierung in C++

Question

ist. Ich habe eine Template-Klasse, die eine vorzeichenlose Integer-Zahl als Template-Parameter verwendet, aber ich muss sicherstellen, dass die Zahl eine Primzahl ist. Ich kann es zum Beispiel im Konstruktor überprüfen, aber es wäre besser, es während der Kompilierung zu tun.

Hier ist die Assert Vorlage Ich verwende:

template <bool statement> 
class Assert; 

template <> 
struct Assert<true> {}; 

Ich kann einfach ein Objekt dieser Art in jedem Stück Code erstellen, die kompiliert werden sollen, meinen Zustand als Parameter verwendet wird, und es gewann Kompiliere nicht, wenn diese Bedingung falsch ist. Das Problem ist, dass ich überprüfen muss, ob eine Zahl prim ist. Lass es n sein.

Ich habe die Idee, eine separate Datei "PrimeTest.h" und versuchen, n durch jede Nummer von n-1 bis 1 zu teilen, indem Sie die gleiche Datei aus dieser Datei enthalten. Das ist, wie ich es verwenden:

#define SUSPECT n 
#include "PrimeTest.h" 

Dies ist die „PrimeTest.h“:

#ifdef SUSPECT 

    #ifndef CURRENT 
     #define CURRENT (SUSPECT-1) 
    #endif // CURRENT 

    #ifndef FINISHED 

    #if CURRENT>100 
     #define IS_PRIME 
     #define FINISHED 
    #else 
     #if SUSPECT%CURRENT==0 
      #define IS_NOT_PRIME 
      #define FINISHED 
     #else 
      #define CURRENT (CURRENT-1) // THAT DOES NOT WORK!!! 
      #include "PrimeTest.h" 
     #endif // SUSPECT % CURRENT != 0 
    #endif 

    #endif // FINISHED 

#endif // SUSPECT 

Aber hier ist das Problem: Ich kann nicht CURRENT in irgendeiner Weise verringern ich tun konnte mit, einschließlich temporärer Werte und # pragma push_macro-Anweisungen. Irgendwelche Ideen, wie man das macht?

Answer 1

Sie benötigen keinen Präprozessor, um etwas zur Kompilierzeit zu berechnen. Normalerweise, wenn die Berechnung benötigt wird, verwenden Sie Metaprogrammierung (oder constexpr Funktionen wie chris in seiner Antwort vorgeschlagen)

Via Metaprogrammierung Sie die Aufgabe lösen können, wie folgt:

Zunächst definieren Sie eine Vorlage der zur Kompilierzeit überprüfen, ob N der gegebene Wert durch D oder einen beliebigen Wert niedriger als D größer als 1.

template <int N, int D> 
struct tmp { 
    static const bool result = (N%D) && tmp<N,D-1>::result; 
}; 

template <int N> 
struct tmp<N,1> { 
    static const bool result = true; 
}; 

der Wert tmp<N,D>::resultdivisble ist, 10 nur wenn die Nummern 2, 3, ... D nicht teilen N.

Mit dem obigen Werkzeug zur Hand, ist is_prime Kompilierung-checker Erstellung ziemlich einfach:

template <int N> 
struct is_prime { 
    static const bool result = tmp<N,N-1>::result; 
}; 

Nun ist der Kompilierung-Wert is_prime<N>::resulttrue ist, wenn N Primzahl ist, und false anders. Der Wert kann an weitere Vorlagen wie die Assert von Ihnen geliefert werden.

Answer 2

Hier ist eine Amateur-Lösung, die für positive Zahlen und zur Kompilierzeit fertig ist, aber es kann nicht zu weit gehen, bevor es wegen einer Rekursionsgrenze bricht. Ich nehme an, Sie könnten einen Quadratwurzelparameter hinzufügen, den Sie manuell berechnen, um es zu ermöglichen, was es jetzt quadriert. Es nutzt die Vorteile von C++ 11's constexpr Funktionen, obwohl, um die Syntax ein bisschen schöner ohne zusätzliche Arbeit zu verwenden. Auf jeden Fall könnte es ein guter Anfang sein und ich freue mich darauf, Antworten zu sehen, die besser funktionieren.

constexpr bool IsPrime(std::size_t N, std::size_t I = 2) { 
    return (N != 2 ? N%I : true) //make 2 prime and check divisibility if not 2 
     && (N >= 2) //0 and 1 are not prime 
     && (I >= N-1 ? true : IsPrime(N, I+1)); //stop when I is too big 
} 

Sie können diese Quadratwurzel sogar für Sie erledigen. Für dieses Beispiel werde ich IsPrime in einen Helfer, so dass IsPrime nur mit N aufgerufen werden:

//basically does ceil(sqrt(N)) 
constexpr std::size_t Sqrt(std::size_t N, std::size_t I = 2) { 
    return I*I >= N ? I : Sqrt(N, I+1); 
} 

//our old IsPrime function with no default arguments; works with sqrt now 
constexpr bool IsPrimeHelper(std::size_t N, std::size_t sqrt, std::size_t I) { 
    return (N != 2 ? N%I : true) 
     && (N >= 2) 
     && (I >= sqrt ? true : IsPrimeHelper(N, sqrt, I+1)); 
} 

//our new prime function: this is the interface for the user 
constexpr bool IsPrime(std::size_t N) { 
    return IsPrimeHelper(N, Sqrt(N), 2); 
} 

Für mich ist diese neue Version arbeitet mit der Nummer 521, wo der andere ist fehlgeschlagen. Es funktioniert sogar mit 9973. Das neue erwartete Hoch sollte ungefähr dem Quadrat des Alten entsprechen. Wenn Sie weiter gehen wollen, könnten Sie sogar IsPrimeHelper um 1 erhöhen, wenn I 2 ist und um 2, wenn I nicht 2 ist. Das würde zu einem neuen Hoch von etwa doppelt so hoch führen.

Answer 3

C++ 11 constexpr Version, die Zahlen der Lage sein, sollte auf jedem Compiler bis zu etwa 1500 zu überprüfen, die die vorgeschlagene Rekursionstiefe Grenze implementiert:

constexpr bool is_prime_helper(std::size_t target, std::size_t check) { 
    return (check*check > target) || 
    (
     (target%(check+1) != 0) 
     && (target%(check+5) != 0) 
     && is_prime_helper(target, check+6) 
    ); 
} 
constexpr bool is_prime(std::size_t target) { 
    return (target != 0) && (target !=1) && 
    ((target == 2 || target == 3 || target == 5) 
    || ((target%2 != 0) && (target%3 != 0) && (target%5)!=0 && 
    is_prime_helper(target, 6))); 
} 

dies zu verbessern, tun wir etwas Spaß mit einem binären Suchbaum:

#include <cstddef> 

constexpr bool any_factors(std::size_t target, std::size_t start, std::size_t step) { 
    return 
     !(start*start*36 > target) 
    && 
    (
    ((step==1) 
     && (
     (target%(start*6+1) == 0) 
     || (target%(start*6+5) == 0) 
    ) 
    ) 
    || 
    ((step > 1) 
     && 
     (
     any_factors(target, start, step/2) 
     || any_factors(target, start+step/2, step/2) 
    ) 
    ) 
); 
} 

, die wir dann wie folgt verwenden:

constexpr bool is_prime(std::size_t target) { 
    // handle 2, 3 and 5 explicitly: 
    return 
    (target == 2 || target == 3 || target == 5) 
    || 
    (
     target != 0 
     && target != 1 
     && target%2 != 0 
     && target%3 != 0 
     && target%5 != 0 
     && !any_factors(target, 1, target/6 + 1) // can make that upper bound a bit tighter, but I don't care 
    ); 
} 
#include <iostream> 
int main() { 
    std::cout << "97:" << is_prime(97) << "\n"; 
    std::cout << "91:" << is_prime(91) << "\n"; 
} 

die ~ log_2(target/6) mal recurse, was bedeutet, dass die Rekursionsgrenze von constexpr Ausdrücken von 512, dass C++ 11 Standard anfordert, dass Compiler als Minimum implementieren, kein Problem mehr ist.

Live example, mit Debugging eingebettet.

Dies funktioniert bis zu den Grenzen von std::size_t auf Ihrem System. Ich habe es mit 111111113 getestet.