Controlla se il numero è primo durante la compilazione in C++

Question

Ho una classe template che accetta un intero senza segno come parametro del modello, ma devo assicurarmi che quel numero sia un numero primo. Posso controllarlo nel costruttore, ad esempio, ma sarebbe meglio farlo durante la compilazione.

Ecco il modello Assert sto usando:

template <bool statement> 
class Assert; 

template <> 
struct Assert<true> {}; 

posso semplicemente creare un oggetto di questo tipo, in ogni pezzo di codice che sta per essere compilato, usando la mia condizione come parametro, e ha vinto compilare se questa condizione è falsa. Il problema è che devo controllare se un numero è primo. Lascia che sia n.

Mi è venuta l'idea di includere un file separato "PrimeTest.h" e provare a dividere n per ogni numero da n-1 a 1 includendo lo stesso file all'interno di quel file. Ecco come lo uso:

#define SUSPECT n 
#include "PrimeTest.h" 

Questo è il "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 

Ma ecco il problema: non riesco a diminuire CORRENTE in alcun modo ho potuto venire con, compresi i valori temporanei e le direttive #pragma push_macro. Qualche idea su come farlo?

Answer 1

Non è necessario il preprocessore per calcolare qualcosa in fase di compilazione. Di solito, quando è necessario il calcolo, si utilizza template metaprogrammazione (o constexpr funzioni come suggerito da Chris nella sua risposta)

Via modello metaprogrammazione è possibile risolvere il compito come segue:

In primo luogo si definisce un modello che può controllare al momento della compilazione se il valore fornito è N divisble da D o qualsiasi valore inferiore D maggiore di 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; 
}; 

il valore tmp<N,D>::result è true solo quando i numeri 2, 3, ... D non dividono N.

Con lo strumento di cui sopra a portata di mano, creando is_prime compile-time checker è abbastanza semplice:

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

Ora il valore in fase di compilazione is_prime<N>::result è true quando N è primo, e false altrimenti. Il valore può essere fornito a ulteriori modelli, come il tuo Assert.

Answer 2

Ecco una soluzione amatoriale che è per numeri positivi e fatta in fase di compilazione, ma non può andare troppo lontano prima che si rompa a causa di un limite di ricorsione. Suppongo che si possa aggiungere un parametro radice quadrata che si calcola manualmente per consentirgli di salire a quello che ora è al quadrato. Sfrutta le funzioni constexpr di C++ 11, tuttavia, per rendere la sintassi un po 'più piacevole da utilizzare senza lavoro extra. In ogni caso, potrebbe essere un buon inizio e non vedo l'ora di vedere risposte che funzionano meglio.

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 
} 

Si può anche fare quella radice quadrata fatta per voi. Per questo esempio, farò IsPrime in un aiuto in modo che IsPrime può essere chiamato solo con N:

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

Per me, questa nuova versione funziona con il numero 521 dove l'altro non è riuscito. Funziona anche con 9973. Il nuovo massimo atteso dovrebbe essere circa il quadrato del vecchio. Se vuoi andare oltre, potresti anche modificare IsPrimeHelper in incrementi di 1 quando I è 2 e 2 quando I non è 2. Ciò porterebbe a un nuovo massimo di circa il doppio di questo.

Answer 3

C++ 11 constexpr versione che dovrebbe essere in grado di controllare i numeri fino a circa il 1500, qualsiasi compilatore che implementa il limite di profondità di ricorsione suggerito:

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

di migliorare questo, facciamo un po 'di divertimento con un binario albero di ricerca:

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

che poi utilizziamo in questo modo:

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

che si ripeterà ~ log_2(target/6) volte, il che significa che il limite di ricorsione delle espressioni constexpr di 512 richieste dallo standard C++ 11 che i compilatori implementano come minimo non è più un problema.

Live example, con debug incorporato.

Questo funzionerà fino in fondo ai limiti di std::size_t sul proprio sistema. L'ho provato con 111111113.