CODEWITHSUNDEEP
c++
Devender Goyal
Devender Goyal

Reputation: 1778

Built in prime checking function

Does C++ have any built in function to check if the number is prime or not. If yes, then in which library?

Below is my implementation. But was just looking if there is any built in function. Searching on Google just gives user based 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;
}

Upvotes: 12

Views: 34664

Answers (6)

Andy Richter
Andy Richter

Reputation: 189

You can do fewer modulus divisions by only checking 6(k)±1 numbers. Primes above 3 are all in that series. 5 6(1) 7 11 6(2) 13 17 6(3) 19 and so on.
All of the series isn't prime, like 25, but all primes are in the series.

int isPrime(long long N) {
        if (N <= 3) return N > 1;
        if (!(N%6==1 || N%6==5)) return false;  // not 6k±1  
        for (long long k6=5; k6 <= sqrt(N)+1; k6+=6) 
                if (N%k6==0 || N%(k6+2)==0) return false;
        return true;
}

There are faster checks for sure. This is pretty fast and is much faster than the n=3,i*i<N division way.

  • The first line gets rid of negative numbers and returns true for 2 and 3
  • The next line knows that any number left is > 3 and may only be prime if (N%6==5 for 6k-1 like 5,11,17,23,29) or (N%6==1 for 6k+1 like 7,13,19,25,31) if it isn't 5 or 1 it cannot be prime and we are done. This one line gets rid of 66% of numbers right away.
  • The loop now goes from 5 to the square root of N. at each iteration we check we check (5,7),(11,13),(17,19)(23,25),(29,31) and so on. If we get an even division we are done. 20% of the remaining non-primes drop out at the first division by 5.
  • If it survives then it is prime, return true.

Upvotes: 0

DAG
DAG

Reputation: 445

template <size_t upper_limit> class prime_table final {
public:
  static_assert(upper_limit >= 2, "upper_limit too tiny");
  prime_table() {
    table_.set();
    table_.reset(0);
    table_.reset(1);

    size_t root = size_t(std::sqrt(upper_limit)) + 1;
    for (size_t pos = 2; pos <= root; ++pos) {
      for (size_t multiplier = 2; pos * multiplier <= upper_limit;
           ++multiplier) {
        table_.reset(pos * multiplier);
      }
    }
  }

  inline bool is_prime(size_t value) { return table_.test(value); }

protected:
  std::bitset<upper_limit + 1> table_;
};

It generates a prime number table then you can use is_prime() to test against a number in range [0, upper_limit]

Upvotes: 0

rwst
rwst

Reputation: 2675

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

Just convert your 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;
}

Upvotes: 2

cprogrammer
cprogrammer

Reputation: 5665

There is no C++ "build-in" function, but you can resolve this with 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 it helps

Upvotes: 1

user784668
user784668

Reputation:

Short answer: no, there's no such function.

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

274) The name of this engine refers, in part, to a property of its period: For properly-selected values of the parameters, the period is closely related to a large Mersenne prime number.

If such function existed, the standard would contain more occurrences of that word, as it would use it to describe the behavior of that function.

Upvotes: 7

Luchian Grigore
Luchian Grigore

Reputation: 258548

No, there's no built-in function that checks for prime.

The solution you posted could be improved on: the 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 map, as to not calculate repeatedly - http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Upvotes: 8

Related Questions