11

C++ 是否有任何内置函数来检查数字是否为素数。如果是，那么在哪个图书馆？

下面是我的实现。但只是在寻找是否有任何内置功能。在 Google 上搜索只是提供基于用户的实现。

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

5 回答 5

8

不，没有检查素数的内置函数。

您发布的解决方案可以改进：i*i如果您只计算一次的平方根，则可以避免N。

如果您知道要检查的数字范围，可以使用筛子和地图，以免重复计算 - http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

于 2012-06-05T12:00:55.610 回答
6

简短的回答：不，没有这样的功能。

唯一一次在标准中使用“prime”一词是 26.5.3.2 中的脚注，这mersenne_twister_engine是描述类模板的地方。脚注说：

274）这个引擎的名称部分地指代它的周期属性：对于正确选择的参数值，周期与一个大的梅森素数密切相关。

如果存在这样的函数，则标准将包含该词的更多出现，因为它将使用它来描述该函数的行为。

于 2012-06-05T12:01:28.047 回答
1

没有 C++“内置”功能，但您可以使用元编程以编译时效率解决这个问题。

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

希望能帮助到你

于 2012-06-05T12:15:28.973 回答
1

广泛可用的 GMP 库具有用于概率素数测试的快速功能，请参阅https://gmplib.org/manual/Number-Theoretic-Functions.html

只需转换您的整数，示例代码：

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;
}
于 2017-07-16T07:34:41.073 回答
0 
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_;
};

它会生成一个素数表，然后您可以使用 is_prime() 来测试范围 [0, upper_limit] 内的数字

于 2020-01-05T10:10:44.710 回答