B 阶乘
最大质因数补丁版
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
int ans = -1;
for (int i = 2; i * i <= n; ++i)
if (n % i == 0) {
int cnt = 0;
while (n % i == 0) {
n /= i;
++cnt;
}
int j = i;
for (int tmp = 0;tmp<cnt; j += i)
for (int k = j; k % i == 0; k /= i) ++tmp;
ans = max(ans, j-i);
}
cout << max(ans, n) << endl;
}
return 0;
} 分解质因数+二分+比对每个质数个数
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 1005;
ll prime_num[maxn], num; //质因数的个数
ll prime[maxn];
const ll mod = 1e9 + 7;
void divid(ll n) //分解正整数n
{
num = 0;
if (n % 2 == 0) {
ll term = 0;
while (n % 2 == 0) {
term++;
n /= 2;
}
prime_num[num] = term;
prime[num++] = 2;
}
for (ll i = 3; i * i <= n; i += 2)
if (n % i == 0) {
ll term = 0;
while (n % i == 0) {
term++;
n /= i;
}
prime_num[num] = term;
prime[num++] = i;
}
if (n > 1) {
prime[num] = n;
prime_num[num++] = 1;
}
}
//假设s为n!的一个质因数,k=n/s,m为不能被s整除的数;则(1s*2s*....*ks)*m=n!-->s^k*k!*m=n!如此递归可求出s^r*m=n!的形式
// s为n!的一个质因数，x为n！中质因数s的个数则x=n/s+n/p^s+...;
ll factory(ll n, ll s) //求n!中质数s的个数的函数
{
ll sum = 0;
while (n) {
n /= s;
sum += n;
}
return sum;
}
bool check(ll x) {
for (int i = 0; i < num; i++) //逐个检索每个质数
if (factory(x, prime[i]) < prime_num[i]) return false;
return true;
}
int main() { //求π(pow(pi,n!/pi)) ,pi为x的质因数
int t;
scanf("%d", &t);
while (t--) {
ll x;
scanf("%lld", &x);
if (x <= 5) {
printf("%lld\n", x);
continue;
}
divid(x);
ll left = 1, right = x, ans = x;
while (left <= right) {
ll mid = (left + right) / 2;
if (check(mid)) { //搜索尽可能小的
ans = mid;
right = mid - 1;
} else
left = mid + 1;
}
printf("%lld\n", ans);
}
return 0;
} 核心在
//假设s为n!的一个质因数,k=n/s,m为不能被s整除的数;则(1s*2s*....*ks)*m=n!-->s^k*k!*m=n!如此递归可求出s^r*m=n!的形式
// s为n!的一个质因数，x为n！中质因数s的个数则x=n/s+n/p^s+...;
ll factory(ll n, ll s) //求n!中质数s的个数的函数
{
ll sum = 0;
while (n) {
n /= s;
sum += n;
}
return sum;
}https://blog.csdn.net/nameofcsdn/article/details/52232438
多个连续素数的和表示正整数
POJ 2739 Sum of Consecutive Prime Numbers
http://poj.org/problem?id=2739
翻译https://blog.csdn.net/woniupengpeng/article/details/53696743
#include <iostream>
#define sscc ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int N=2000,n=10000;
int prime[N],total=0;
bool chk(int k) {
for(int i=0; i<total; i++)
if(k%prime[i]==0)
return false;
return true;
}
void pre() {
for(int i=2; i<n; i++)
if(chk(i))
prime[total++]=i;
prime[total]=n+1;
}
int main() {
pre();
int m;
while(cin>>m,m) {
int ans=0;
for(int i=0; prime[i]<=m; i++) {
int cnt=0;
for(int j=i; j<total,cnt<m; j++)
cnt+=prime[j];
if(cnt==m)
++ans;
}
cout<<ans<<endl;
}
//cout<<"0";
return 0;
} 求1--r中与n互素数的个数
容斥原理的应用，具体分析见下面代码注释：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n, r;
//计算1--r中与n互素数的个数
//思路跟计算n的欧拉函数值一样,但这里没有公式化简
//所以采用k位2进制进行模拟(k表示n在r范围内素因子的个数)
//从1--2^k-1中的每一位数的二进制中1的分布表示刚好可以对应
//不同的因子组合情况
int solve() {
int i, j, k = 0, ans = 0;
int prime[100]; // n的素因子表
for (i = 2; i * i <= n; i++) //求出1--r中n所有的素因子,控制条件必须是i*i,否则会超时
if (n % i == 0) {
prime[k++] = i;
while (n % i == 0) n = n / i;
}
if (n > 1) //除了最后n未除尽的情况外,i=2,3或n为素数的情况也都由此处理
prime[k++] = n;
for (i = 1; i < (1 << k); i++) // i<<N表示2^N
{
j = i;
int cnt = 0, mult = 1; // mult用于记录每一种情况下因子的最小公倍数
int m = 0; // m用于记录二进制的位数
while (j) {
if (j & 1) {
cnt++; //记录二进制中1的个数,即因子的个数
mult = mult * prime[m];
}
j = j >> 1; // j右移一位
m++;
}
int cur = r / mult; // 1--r中能被mult整除数的个数
if (cnt % 2) //奇数个因子情况
ans += cur;
else
ans -= cur;
}
return r - ans;
}
int main() {
while (cin >> r >> n) {
int n1 = n;
int ans = solve();
cout << "1--" << r << "中与" << n1 << "互素数的个数为: " << ans << endl;
}
return 0;
}
原文链接：https: // blog.csdn.net/acm_lkl/article/details/38520619
求一个数的所有因数+质因数分解【数论】
https://blog.csdn.net/Z_sea/article/details/82118417
京公网安备 11010502036488号