Built-in Check Function

Question

C ++ has a built-in function to check if a number is prime or not. If so, in which library?

Below is my implementation. But he just looked to see if there was a built-in function. A google search just gives you custom implementations.

int isprime(int N){ if(N<2 || (!(N&1) && N!=2)) return 0; for(int i=3; i*i<=N; i+=2){ if(!(N%i)) return 0; } return 1; } 

Answer 1

Short answer: no, there is no such function.

The only time the word "prime" is used in the standard is the footnote in 26.5.3.2, which describes the template class mersenne_twister_engine . The footnote says:

274) The name of this engine refers, in particular, to the property of its period: for correctly selected parameter values, the period is closely related to a large Mersenne prime.

If such a function exists, the standard will contain more occurrences of this word, since it will use it to describe the behavior of this function.

Answer 2

No, there is no built-in function that checks for simple.

The solution you posted can be improved: i*i can be avoided if you only calculate the square root of N once.

If you know the range of the number you want to check, you can use a sieve and a card to not recalculate - http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Answer 3

The widely available GMP library has a quick function for probabilistic simple testing, see https://gmplib.org/manual/Number-Theoretic-Functions.html

Just convert an integer, example code:

 bool is_prob_prime(long l) { mpz_t bigint; mpz_init_set_si(bigint, l); bool ret = mpz_probab_prime_p(bigint, 25) > 0; mpz_clear(bigint); return ret; } 

Answer 4

There is no C ++ built-in function, but you can solve this problem using compile-time efficiency using metaprogramming.

 template <int i> struct D { D(void *); operator int(); }; template <int p, int i> struct is_prime { enum { prim = (p%i) && is_prime<(i>2?p:0), i>::prim }; }; template <int i> struct Prime_print { Prime_print<i-1> a; enum { prim = is_prime<i,i-1>::prim }; void f() { D<i> d = prim; } }; struct is_prime<0,0> { enum { prim = 1 }; }; struct is_prime<0,1> { enum { prim = 1 }; }; struct Prime_print<2> { enum { prim = 1 }; void f() { D<2> d = prim; } }; void foo() { Prime_print<10> a; } 

Hope this helps