[数论第一节]质数/约数

  • 数论

    • 质数

      • 在大于1的整数中,只包含1和本身这两个约数,就被称为质数,也叫素数
      • 质数的判定
        • 试除法
          • 遍历2-n,若有约数则不为质数 O(n)
          • 优化:
            • d整除n,则n/d也整除n,约数总是成对出现,只要找较小的约数,即取d <= n/d,则d <= sqrt(n) 只用遍历2-sqrt(n) O(sqrt(n))
            • 不用 i * i <= n ,i过大会溢出
            • sqrt()函数较慢,只用遍历 d--n/d,即限制范围为 i--n/i
          • 代码:
            //不用for(int i = 1; i * i <= n; ++ i) i * i 会溢出
            //不用for(int i = 1; i <= sqrt(n); ++ i) sqrt() 函数缓慢
            //用for(int i = 1; i <= n / i; ++ i)  不会溢出,快
            bool is_prime(int x){
            	if(x < 2) return false;
            	for(int i = 2; i <= n / i; ++ i)
            		if(n % i == 0) return false;
            	return true;
            }
            
      • 分解质因数
        • 试除法
          • 遍历2-n,找因子
          • n最多有一个大于sqrt(n)的因子,因此只用在2-sqrt(n)中找因子,最后判断最后一个因子是否为大于sqrt(n)的因子
          • 代码:
            //暴力做法
            void divide(int n){
            	for(int i = 2; i <= n; ++ i){
            		if(n % i == 0){
            			int s = 0; //i的个数
            			while(n % i == 0){
            				n /= i; //除干净
            				s ++ ;
            			}
            			cout << i << s << endl;
            		}
            	}
            }
            //优化
            void divide(int n){
            	for(int i = 2; i <= n / i; ++ i){
            		if(n % i == 0){
            			int s = 0;
            			while(n % i == 0){
            				n /= i;
            				s ++ ;
            			}
            			cout << i << s << endl;
            		}
            	}
            	if(n > 2) cout << n << 1;//n就是最后大于sqrt(n)的因子
            }
            
      • 筛选质数
        • 埃氏筛法
          • 从2-n,将每个数的倍数删掉,那么剩下的数就是质数 O(nln(n))
          • 优化:
            • 任何一个合数都可以拆成若干素数之积,因此只用将素数的倍数删掉 O(nln(ln(n))) ~ O(n)
          • 代码:
            int primes[N];
            int st[N];//标记是否被筛过
            void get_primes(int n){
            	int cnt = 0;
            	for(int i = 2; i <= n; ++ i){
            		if(!st[i]){ //没有被筛过,说明是质数
            			primes[ ++ cnt] = i;
            			//筛该质数的所有倍数
            			for(int j = i + i; j <= n; j += i) st[j] = 1;
            		}
            	}
            }
            
        • 线性筛法
          • 数据大小在107左右线性筛法比埃氏筛法快一倍,106左右差不多
          • n只会被它的最的最小质因子筛掉,利用最小质因子筛掉合数
          • 代码:
            int primes[N];
            int st[N];
            void get_primes(int n){
            	int cnt = 0;
            	for(int i = 2; i <= n; ++ i){
            		if(!st[i]) primes[ ++ cnt] = i;//没有被筛掉就是质数
            		for(int j = 1; primes[j] <= n / i; ++ j){//从小到大遍历质数
            			st[primes[j] * i] = 1; //筛掉合数,若x是合数,当i遍历到x时,一定会先遍历到x的最小质因子prime,所以此时prime进入primes数组,当i遍历到x/prime时,x = prime*i会被筛掉,所以每个合数都能被筛掉,并且是在遍历到该合数之前被筛掉
            			if(i % pimes[j] == 0) break; //i是合数筛掉i,i在之前就被标记过,所以不用再标记
            		} 
            	}
            }
            
    • 约数

      • 求所有约数

        • 试除法
          • 代码:
            vector<int> get_divisors(int n){
            	vector<int> res;
            	for(int i = 1; i <= n / i; ++ i){
            		if(n % i == 0){
            			res.push_back(i);
            			if(i != n / i) res.push_back(n / i);
            		}
            	}
            	sort(res.begin(), res.end());
            	return res;
            }
            
      • 约数的个数

        • \(N = p_1^{a_1} · p_2^{a_2} · p_3^{a_3} ··· ·p_n^{a_n}\) 其中p为N的所有质因子
        • 则N的约数个数为:\((a_1+1)(a_2+1)(a_3+1)···(a_n+1)\)
          • 代码:
            const int mod = 1e7 + 10;
            unordered_map<int, int> primes;//hash表存储每个质数有多少
            void get_primes(int n){
            	for(int i = 2; i <= n / i; ++ i){
            		while(n % i == 0){
            			n /= i;
            			primes[i] ++ ;
            		}
            	}
            	if(n > 1) primes[n] ++ ;
            }
            for(int i = 1; i <= n; ++ i) get_primes(a[i]);
            long long res = 0;
            for(auto p : primes) res = res * (p.second + 1) % mod;
            
        • 则N的约数总和为:\((p_1^{0}+p_1^{2}+···+p_1^{n})(p_2^{0}+p_2^{1}+···+p_2^{n})···(p_n^{0}+p_n^{1}+···+p_n^{n})\)
          • 代码:
            const int mod = 1e7 + 10;
            unordered_map<int, int> primes;
            void get_primes(int n){
            		for(int i = 2; i <= n / i; ++ i){
            			while(n % i == 0){
            				n /= i;
            				primes[i] ++ ;
            			}
            		}
            		if(n > 1) primes[n] ++ ;
            	}
            	for(int i = 1; i <= n; ++ i) get_primes(a[i]);
            	long long res = 1;
            	for(auto p : primes){
            		long long t = 1;
            		int a = p.first, b = p.second;
            		while(b -- ) t = (t * a + 1) % mod;
            		res = res * t % mod;
            	}
            
      • 最大公约数

        • 辗转相除法(欧几里得算法)O(logn)
        • a|b, a|c, 则 a|(b+c), 则a|(bx + cy)
        • 求a与b的最大公约数,设其公约数为c,则c|a, c|b, c|(ax + by), 设a = kb + m, 则m = a - kb, 则c|m, 又m = a % b, 则 c|(a % b), 即a与b的最大公约数,也是a%b的公约数,即gcd(a, b) = gcd(b, a % b)
        • 代码:
          int gcd(int a, int b){
          	return b ? gcd(b, a % b) : a;
          }
          

热门相关:冉冉心动   大妆   本法官萌萌哒   超级名模   后福