算法笔记-第五章-质因子分解

小试牛刀

质因子2的个数

#include<cstdio>  
int main()  
{int n;  scanf_s("%d", &n);  int count = 0;  while (n % 2 == 0)  {count++;  n /= 2;  }printf("%d", count);  return 0;  
}

丑数

#include <cstdio>int main() {int n;scanf("%d", &n);while (n % 2 == 0) {   n /= 2;   }while (n % 3 == 0) {   n /= 3;   }while (n % 5 == 0) {   n /= 5;   }printf(n == 1 ? "Yes" : "No");   return 0;   
}

质因子分解

#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;const int MAXN = 1000 + 1;
bool isPrime[MAXN];//布尔函数，用于指定可以为倍数的因子
vector<int> primes;//存储指定的倍数因子void getPrimes(int n) 
{memset(isPrime, true, sizeof(isPrime));//对于布尔数组isprime进行复制truefor (int i = 2; i <= n; i++) //可以为倍数的从2开始到n(数的开方){if (isPrime[i]) //选取可以为倍数的因子{primes.push_back(i);//放到数组当中//并且下面对于访问过的倍数进行标记for (int j = i + i; j <= n; j += i) {isPrime[j] = false;}}}
}int main() {int n;scanf("%d", &n);getPrimes((int)sqrt(1.0 * n));//数的开方（带入到访问因子当中）for (int i = 0; i < primes.size() && n > 1; i++) //下面是进行因子判断和统计了{int counter = 0;//每一次都是统计每一个因子的数目while (n > 1 && n % primes[i] == 0) {counter++;n /= primes[i];  }if (counter > 0) //统计后进行输出数据  {printf("%d %d\n", primes[i], counter);  }}if (n > 1)   {printf("%d 1", n);  }return 0;  
}

最小最大质因子

//最小最大质因子
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;const int INF = 0x3f;//表示无穷大数
const int MAXN = 1000 + 1;
bool isPrime[MAXN];
vector<int> primes;void getPrimes() 
{memset(isPrime, true, sizeof(isPrime));//将布尔函数进行赋值for (int i = 2; i < MAXN; i++){if (isPrime[i]){primes.push_back(i);for (int j = i + i; j < MAXN; j += i) //将倍数因子进行标记{isPrime[j] = false;}}}
}int main() 
{int n, x;scanf("%d", &n);getPrimes();//将倍数因子进行标记操作int minFactor = INF, maxFactor = 0;for (int i = 0; i < n; i++) {scanf("%d", &x);for (int j = 0; j < primes.size() && x > 1; j++)   {int counter = 0;  while (x > 1 && x % primes[j] == 0)//求得因子  {counter++;//统计因子数目  x /= primes[j];  }if (counter > 0) //取得因子最小值和因子最大值  {minFactor = min(minFactor, primes[j]);  maxFactor = max(maxFactor, primes[j]);  }}//最后条件：x除以prime[j]还有数且>1时候  if (x > 1)   {minFactor = min(minFactor, x);  maxFactor = max(maxFactor, x);  }}printf("%d %d", minFactor, maxFactor);  return 0;  
}

约数个数

#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;const int MAXN = 1000 + 1;
bool isPrime[MAXN];
vector<int> primes;void getPrimes(int n) 
{memset(isPrime, true, sizeof(isPrime));for (int i = 2; i <= n; i++) {if (isPrime[i]) {primes.push_back(i);for (int j = i + i; j <= n; j += i){isPrime[j] = false;}}}
}int main() {int n;scanf("%d", &n);getPrimes((int)sqrt(1.0 * n));int result = 1;for (int i = 0; i < primes.size() && n > 1; i++) {int counter = 0;while (n > 1 && n % primes[i] == 0) {counter++;n /= primes[i];}if (counter > 0) {result = result * (counter + 1);}}if (n > 1) {result = result * 2;}printf("%d", result);return 0;
}