• 數(shù)論

  • 質(zhì)數(shù)

    • 在大于1的整數(shù)中，只包含1和本身這兩個約數(shù)，就被稱為質(zhì)數(shù)，也叫素數(shù)

    • 質(zhì)數(shù)的判定

      • 試除法

        • 遍歷2-n，若有約數(shù)則不為質(zhì)數(shù) O(n)
        • 優(yōu)化：
          • d整除n，則n/d也整除n，約數(shù)總是成對出現(xiàn)，只要找較小的約數(shù)，即取d <= n/d，則d <= sqrt(n) 只用遍歷2-sqrt(n) O(sqrt(n))
          • 不用 i * i <= n ，i過大會溢出
          • sqrt()函數(shù)較慢，只用遍歷 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() 函數(shù)緩慢
          //用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;
          }
          

    • 分解質(zhì)因數(shù)

      • 試除法

        • 遍歷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的個數(shù)
          			while(n % i == 0){
          				n /= i; //除干凈
          				s ++ ;
          			}
          			cout << i << s << endl;
          		}
          	}
          }
          //優(yōu)化
          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)的因子
          }
          

    • 篩選質(zhì)數(shù)

      • 埃氏篩法

        • 從2-n，將每個數(shù)的倍數(shù)刪掉，那么剩下的數(shù)就是質(zhì)數(shù) O(nln(n))
        • 優(yōu)化：
          • 任何一個合數(shù)都可以拆成若干素數(shù)之積，因此只用將素數(shù)的倍數(shù)刪掉 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]){ //沒有被篩過，說明是質(zhì)數(shù)
          			primes[ ++ cnt] = i;
          			//篩該質(zhì)數(shù)的所有倍數(shù)
          			for(int j = i + i; j <= n; j += i) st[j] = 1;
          		}
          	}
          }
          

      • 線性篩法

        • 數(shù)據(jù)大小在10^{7左右線性篩法比埃氏篩法快一倍，10}6左右差不多
        • n只會被它的最的最小質(zhì)因子篩掉，利用最小質(zhì)因子篩掉合數(shù)
        • 代碼：

          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;//沒有被篩掉就是質(zhì)數(shù)
          		for(int j = 1; primes[j] <= n / i; ++ j){//從小到大遍歷質(zhì)數(shù)
          			st[primes[j] * i] = 1; //篩掉合數(shù)，若x是合數(shù)，當i遍歷到x時，一定會先遍歷到x的最小質(zhì)因子prime，所以此時prime進入primes數(shù)組，當i遍歷到x/prime時，x = prime*i會被篩掉，所以每個合數(shù)都能被篩掉，并且是在遍歷到該合數(shù)之前被篩掉
          			if(i % pimes[j] == 0) break; //i是合數(shù)篩掉i，i在之前就被標記過，所以不用再標記
          		} 
          	}
          }
          

  • 約數(shù)

    • 求所有約數(shù)

      • 試除法

        • 代碼：

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

    • 約數(shù)的個數(shù)

      • 若\(N = p_1^{a_1} · p_2^{a_2} · p_3^{a_3} ··· ·p_n^{a_n}\) 其中p為N的所有質(zhì)因子
      • 則N的約數(shù)個數(shù)為：\((a_1+1)(a_2+1)(a_3+1)···(a_n+1)\)
        • 代碼：

          const int mod = 1e7 + 10;
          unordered_map<int, int> primes;//hash表存儲每個質(zhì)數(shù)有多少
          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的約數(shù)總和為：\((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;
          	}
          

    • 最大公約數(shù)

      • 輾轉(zhuǎn)相除法（歐幾里得算法）O(logn)
      • a|b, a|c, 則 a|(b+c), 則a|(bx + cy)
      • 求a與b的最大公約數(shù)，設(shè)其公約數(shù)為c，則c|a, c|b, c|(ax + by), 設(shè)a = kb + m, 則m = a - kb, 則c|m, 又m = a % b, 則 c|(a % b), 即a與b的最大公約數(shù)，也是a%b的公約數(shù)，即gcd(a, b) = gcd(b, a % b)
      • 代碼：

        int gcd(int a, int b){
        	return b ? gcd(b, a % b) : a;
        }
        

文章來源地址http://www.zghlxwxcb.cn/news/detail-633014.html

到了這里，關(guān)于[數(shù)論第一節(jié)]質(zhì)數(shù)/約數(shù)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！