Sprawdź, czy liczba jest liczbą pierwszą podczas kompilacji w C++

Question

Mam klasę szablonu, która pobiera liczbę całkowitą bez znaku jako parametr szablonu, ale muszę się upewnić, że liczba jest liczbą pierwszą. Mogę to sprawdzić na przykład w konstruktorze, ale lepiej byłoby zrobić to podczas kompilacji.

Oto szablon Assert Używam:

template <bool statement> 
class Assert; 

template <> 
struct Assert<true> {}; 

mogę po prostu utworzyć obiekt tego typu w każdym kawałku kodu, który zostanie skompilowany przy użyciu mój stan jako parametr, i wygrał kompiluje, jeśli ten warunek jest fałszywy. Problem polega na tym, że muszę sprawdzić, czy jakaś liczba jest najlepsza. Niech to będzie n.

Wpadłem na pomysł włączenia osobnego pliku "PrimeTest.h" i próby podzielenia n przez każdy numer od n-1 do 1 poprzez włączenie tego samego pliku z wewnątrz tego pliku. To jak go używać:

#define SUSPECT n 
#include "PrimeTest.h" 

Jest to „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 

Ale tutaj jest problem: nie mogę zmniejszyć prąd w żaden sposób nie mogłem wymyślić, w tym wartości tymczasowe i dyrektywy #pragma push_macro. Jakieś pomysły, jak to zrobić?

Answer 1

Nie potrzebujesz preprocesora, aby obliczyć coś podczas kompilacji. Zazwyczaj, gdy potrzebne jest obliczenie, należy użyć szablonu meta-programowych (lub constexpr funkcje sugerowane przez Chris w swojej odpowiedzi)

Via szablonu metaprogramowanie można rozwiązać zadanie w następujący sposób:

Najpierw trzeba zdefiniować szablon, który może sprawdzić w czasie kompilacji, jeśli podana wartość N jest divisble przez D lub dowolnej wartości niższej niż D większa niż 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; 
}; 

wartość tmp<N,D>::result jest true tylko wtedy, gdy liczby 2, 3, ... D nie dzielą N.

Z powyższego narzędzia pod ręką, tworząc is_prime kompilacji sprawdzania jest dość proste:

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

Teraz wartość czasu kompilacji is_prime<N>::result jest true gdy N jest pierwsza, a false inaczej. Wartość może zostać dostarczona do dalszych szablonów, takich jak Assert.

Answer 2

Oto amatorskie rozwiązanie, które jest dla liczb dodatnich i wykonane w czasie kompilacji, ale nie może iść zbyt daleko, zanim się zepsuje z powodu ograniczenia rekursji. Przypuszczam, że możesz dodać parametr pierwiastka kwadratowego, który obliczysz ręcznie, aby umożliwić mu osiągnięcie tego, co teraz robi do kwadratu. Korzysta jednak z funkcji C++ 11 constexpr, aby składnia była nieco przyjemniejsza w użyciu bez dodatkowej pracy. W każdym razie może to być dobry początek i czekam na odpowiedź, która działa lepiej.

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 
} 

Możesz nawet zrobić dla ciebie ten pierwiastek kwadratowy. W tym przykładzie, zrobię IsPrime do pomocnika, tak aby IsPrime można nazwać tylko 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); 
} 

dla mnie, ta nowa wersja działa z numerem 521, gdzie drugi niepowodzeniem. Działa nawet z 9973. Nowe oczekiwane maksimum powinno przypominać kwadrat starego. Jeśli chcesz pójść dalej, możesz nawet zmodyfikować IsPrimeHelper, aby zwiększyć o 1, gdy I wynosi 2, a o 2, gdy I nie jest 2. To prowadzi do nowego maksimum około dwa razy większego.

Answer 3

C++ 11 constexpr wersję, która powinna być w stanie sprawdzić numery do około 1500 na dowolnym kompilatorem, który implementuje sugerowane ograniczenie głębokości rekurencji:

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

poprawić ten, robimy trochę zabawy z binarnym szukaj drzewa:

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

których używamy tak:

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

, który będzie się powtarzał ~ log_2(target/6) razy, co oznacza, że ​​limit rekurencji wynoszący constexpr wyrażenia 512, że standard C++ 11 żąda, aby kompilatory zaimplementowały jako minimum, nie stanowi już problemu.

Live example, z wbudowanym debugowaniem.

To zadziała w zasadzie na granicach std::size_t w twoim systemie. Przetestowałem go pod numerem 111111113.