C++

Question

numaralı derlemede derlemenin asal sayı olup olmadığını kontrol edin Bir işaretsiz tamsayıyı şablon parametresi olarak alan bir şablon sınıfına sahibim, ancak bu numaranın bir asal olduğundan emin olmalıyım. Örneğin kurucuda kontrol edebilirim, ancak derleme sırasında bunu yapmak daha iyi olurdu.

İşte kullanıyorum belirt şablon var: Ben sadece parametre olarak benim koşulunu kullanarak, derlenmiş olacak kodun herhangi bir parçasında bu tip bir nesne oluşturabilir

template <bool statement> 
class Assert; 

template <> 
struct Assert<true> {}; 

ve o kazandı Bu koşul yanlışsa derleme. Sorun şu ki, bazı rakamların asal olup olmadığını kontrol etmek zorundayım. Bırak n olsun.

"PrimeTest.h" adlı ayrı bir dosya ekleme ve n-1'den 1'e her dosyaya aynı dosyayı dahil ederek n'ye bölme girişiminde bulunmayı düşündüm.

#define SUSPECT n 
#include "PrimeTest.h" 

Bu "PrimeTest.h" dir:

#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 

Ama burada sorun: Ben ile gelebilir hiçbir şekilde CURRENT azaltma olamaz, Ben onu nasıl kullandığımızdır geçici değerler ve #pragma push_macro yönergeleri dahil. Herhangi bir fikir nasıl yapılır?

Answer 1

Derleme zamanında bir şey hesaplamak için önişlemciye ihtiyacınız yoktur.

İlk yapabilirsiniz şablon tanımlamak: hesaplama gerektiğinde aşağıdaki gibi şablon metaprogramlama Via

görevi çözebilir (onun cevabını chris tarafından önerildiği gibi ya constexpr işlevleri) Genellikle, şablon metaprogramming kullanmak verilen değer ND veya daha düşük D daha büyük 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; 
}; 

değeri tmp<N,D>::resultolan herhangi bir değer ile divisble ise derleme zamanında kontrol 10 sadece 2, 3, ... D numaraları N'u bölmediğinde.N asal olduğu zaman

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

Şimdi derleme zamanı değeri is_prime<N>::result true ve aksi false: is_prime derleme zamanı denetleyicisi oluşturma el altında yukarıdaki araç ile

oldukça kolaydır. Değer, Assert sizinki gibi başka şablonlara sunulabilir.

Answer 2

İşte pozitif sayılar için ve derleme zamanında yapılan bir amatör çözüm, ama bir yineleme sınırına bağlı olarak kırılmadan önce çok uzak gidebilir. Şimdi, karenin şimdiki haline gelmesine izin vermek için el ile hesapladığınız bir kare kök parametresi ekleyebileceğinizi varsayalım. C + + 11'in constexpr işlevlerinden yararlanırken, sözdizimini fazladan çalışmadan kullanmak için biraz daha güzel hale getirir. Her durumda, iyi bir başlangıç ​​olabilir ve daha iyi çalışan cevapları görmeyi dört gözle bekliyorum.

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 
} 

Bu kare kökü sizin için bile yapabilir. Bu yeni sürümü diğer başarısız numara 521 ile çalışır, Benim için

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

: Bu örnekte, ben IsPrime sadece N ile çağrılabilir böylece bir yardımcı haline IsPrime yapacağız. Hatta 9973 ile çalışır. Yeni beklenen yüksek, eskinin karesiyle ilgili olmalıdır. Daha ileri gitmek isterseniz, 'u, I 2 olduğunda ve 1 ile I 2 olmadığında 1 arttırmak için modifiye edebilirsiniz. Bu, bunun yaklaşık iki katı yeni bir yüksekliğe yol açacaktır.

Answer 3

C++ 11 önerilen yineleme derinliği limitini uygulayan herhangi bir derleyici üzerinde kabaca 1500 kadar numaralarını kontrol etmek mümkün olmalıdır constexpr sürümü:

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

bu sayıyı artırmak için, bir programla ilgili bir eğlence yapmak arama ağacı:

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

o zaman böyle kullanın:

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

,kere tekrarlanır; bu da, C++ 11 standardının derleyicilerin minimum olarak uyguladığı 512 ifadesinin constexpr ifadesinin özyineleme sınırının artık bir sorun olmadığı anlamına gelir. Gömülü hata ayıklama ile birlikte

Live example.

Bu, sisteminizde std::size_t sınırlarını temel alarak çalışır. 111111113 ile test ettim.