您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

素数问题常见解法

素数

素数又称质数,是除了1和本身之外不能被其他数整除的一类数字。用数学语言描述即是,对给定的正整数n,如果对于任意的正整数a(1<a<n),都有n%a!=0成立,那么称n素数;否则称为合数
注:1 既不是素数也不是合数。

素数的判断

一个整数n如果不能被2,3,...,n-1整除,那么n为素数。使用遍历的方法判断,时间复杂度为O(n)。但在某些数据量大的题目中,该复杂度实际有点大,需要更快的方法。
注意到:如果在2~n-1中存在n的约数,设为k,即n%k==0,那么由k*(n/k)==n可知,n/k也是n的一个约数。且kn/k中一定满足其中一个小于等于sqrt(n),另一个大于等于sqrt(n)。因此只需判断n能否被2,3,...,sqrt(n)中的一个整除,即可判断是否为素数。该算法时间复杂度为O(sqrt(n))

代码如下:

bool is_prime(int n) {
  if (n <= 1) {
    return false;
  } else {
    for (int i = 2; i * i <= n; i++) {
      if (n % i == 0) return false;
    }
    return true;
  }
}

素数表的获取

通过判断是否为素数,可以直接得出1~n范围内的所有素数,即从1~n开始枚举,如果是素数就加入素数表。枚举时间复杂度为O(n),判断是否为素数时间复杂度为O(sqrt(n)),总的时间复杂度为O(n*sqrt(n))

求100以内的素数表
代码如下:


int prime[MAXN], p_num = 0; //prime存放所有的素数,p_num为素数的个数
bool p[MAXN] = {0};    //p[i]==ture即为素数 
void find_prime() {
  for (int i = 1; i < MAXN; i++) {
    if (is_prime(i)) {
      prime[p_num++] = i;
      p[i] = true;
    }
  }
}

完整的代码如下:

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 101;
bool is_prime(int n) {
  if (n <= 1) {
    return false;
  } else {
    for (int i = 2; i * i <= n; i++) {
      if (n % i == 0) return false;
    }
    return true;
  }
}

int prime[MAXN], p_num = 0;  // prime存放所有的素数,p_num为素数的个数
bool p[MAXN] = {0};          // p[i]==ture即为素数
void find_prime() {
  for (int i = 1; i < MAXN; i++) {
    if (is_prime(i) == true) {
      prime[p_num++] = i;
      p[i] = true;
    }
  }
}

int main() {
  find_prime();
  for (int i = 0; i < p_num; i++) {
    printf("%d", prime[i]);
  }
  return 0;
}

埃氏筛法(Eratosthenes)

上述的算法对于10^5级别的都可以承受,但如果数字范围更大,那么将会崩溃。使用埃氏筛法时间复杂度可低至O(nloglogn)。该算法从小到大枚举所有的数,对每一个素数,筛去它的所有倍数,剩下的都是素数了。

举例子说明:求1~15所有的素数。
①2是素数(唯一需要事先确定的),因此筛去所有2的倍数,即{4,6,8,10,12,14},剩{2,3,5,7,9,11,13,15}。
②3没有被筛去,因此3是素数,筛去3所有的倍数,即{6,9,12,15},剩{2,3,5,7,11,13}。
③4已经被筛去,因此4不是素数。
④5没有被筛,因此5是素数,筛去所有5的倍数,即{10,15},剩{2,3,5,7,11,13}。
⑤6已经被筛去,因此6不是素数。
⑥7没有被筛去,因此7是素数,筛去所有7的倍数,即{14},剩{2,3,5,7,11,13}。

以此类推…
最终得到所有素数,即{2,3,5,7,11,13}。
由例子可以发现,如果到达某个数x时,它没有被前面的数筛掉,那么它就是素数。

100以内素数代码如下:

const int MAXN = 101;
int prime[MAXN], p_num = 0;
bool p[MAXN] = {0};  // i is a prime,return false
void find_prime() {
  for (int i = 2; i < MAXN; i++) {
    if (p[i] == false) {  // if i is a prime
      prime[p_num++] = i;
      for (int j = i + i; j < MAXN; j += i) {
        p[j] = true;
      }
    }
  }
}

总结

  1. 1不是素数,也不是合数;
  2. 涉及到素数问题,通常打表是一个不错的方法;
  3. 素数的表长最少要比n大于1;
  4. 注意时间复杂度。

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进