绝对素数
绝对素数是指一个素数在其十进制表示下，无论是从左向右读还是从右向左读，所得到的数仍然是素数。
例如，13 是一个素数，从右向左读是 31，31 也是素数，所以 13 是一个绝对素数。
#include <iostream>
#include <cmath>
using namespace std;
bool isPrime(int num) {
if (num < 2) {
return false;
}
for (int i = 2; i <= sqrt(num); i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
bool isAbsPrime(int num) {
int reversedNum = 0, temp = num;
while (temp > 0) {
reversedNum = reversedNum * 10 + temp % 10;
temp /= 10;
}
return isPrime(num) && isPrime(reversedNum);
}
int main() {
int num;
while(cin >> num){
if (isAbsPrime(num)) {
cout << num << " 是绝对素数" << endl;
}
else {
cout << num << " 不是绝对素数" << endl;
}
}
return 0;
}
函数 isPrime：用于判断一个数是否为素数。
如果数字小于 2 ，直接返回 false ，因为 0 和 1 不是素数。从 2 到该数的平方根进行遍历，如果能被整除则返回 false ，遍历结束都不能整除则返回 true 。
函数 isAbsPrime：用于判断一个数是否为绝对素数。
首先定义两个变量，reversedNum 用于存储反转后的数字，temp 用于临时存储原始数字。通过一个循环将数字反转，每次取出原数字的最后一位加到 reversedNum 上，并将原数字除以 10 然后判断原始数字和反转后的数字是否都是素数，如果都是则返回 true ，否则返回 false 。
main 函数：定义一个整数 num 用于接收输入。通过一个 while 循环不断读取输入的数字调用 isAbsPrime 函数来判断输入的数字是否为绝对素数，并根据结果输出相应的信息。
证明：绝对素数的各位上不可以同时出现1,3,7,9
假设存在一个绝对素数，其各位上同时出现了 1、3、7、9。由于是绝对素数，那么其反转后的数也是素数。考虑数字的末尾数字，如果末尾是 1，反转后末尾是 1 ，但如果末尾是 3、7、9 ，反转后末尾变为 3、7、9 。对于以 3、7、9 结尾的数，必然能被 3 整除（一个数各位数字之和能被 3 整除，这个数就能被 3 整除）。
例如，假设这个数是 abc9 ，反转后是 9cba ，那么 9cba 各位数字之和为 9 + c + b + a ，因为 9 能被 3 整除，所以只要 c + b + a 能被 3 整除，9cba 就能被 3 整除，不是素数。同理，对于以 3、7 结尾的情况也能类似推导。所以，绝对素数的各位上不可以同时出现 1、3、7、9 。
整数唯一分解定理
每个大于 1 的正整数都可以唯一地表示为若干个质数的乘积，且这些质数按照从小到大的顺序排列，其指数也都是唯一确定的。
vector<int> factor(int x) {
vector<int> ret;
for (int i = 2; i * i <= x; ++i)
while (x % i == 0) {
ret.push_back(i);
x /= i;
}
if (x > 1)
ret.push_back(x);
return ret;
}
数论基础：它是数论研究中的基础定理，为许多其他定理和问题的解决提供了关键的理论依据。
简化问题：在解决一些涉及整数性质和运算的问题时，将整数分解为质因数的乘积可以使问题变得更加清晰和易于处理。
密码学：在现代密码学中，尤其是公钥密码体制，如 RSA 算法，整数的唯一分解性质起到了核心作用。
素数筛法
素数筛法是一种用于找出一定范围内素数的算法。
埃氏筛法思想
- 基本思路：先将 2 到指定上限的所有数放入一个数组。从 2 开始，将其倍数标记为合数。然后遍历到下一个未标记的数，重复这个过程，直到遍历完所有小于等于上限的数。
- 例如，要找出 1 到 100 之间的素数。首先标记 2 的倍数（4、6、8、... 、100）为合数。然后处理 3，标记 3 的倍数（6、9、12、... ）为合数。接着处理 5 ，以此类推，最后未被标记的就是素数。
const int N = 1e7;
bool isprime[N + 1];
void eratos(int n) {
int i, j;
isprime[0] = isprime[1] = false;
for (i = 2; i <= n; i++)
isprime[i] = true;
for(i=2;i*i<=n;++i)
if (isprime[i]) {
for (j = i * i; j <= n; j += i)
isprime[j] = false;
}
}
#include <iostream>
#include <vector>
using namespace std;
void sieveOfEratosthenes(int n) {
vector<bool> isPrime(n + 1, true);
for (int p = 2; p * p <= n; p++) {
if (isPrime[p]) {
for (int i = p * p; i <= n; i += p) {
isPrime[i] = false;
}
}
}
for (int p = 2; p <= n; p++) {
if (isPrime[p]) {
std::cout << p << " ";
}
}
}
int main() {
int n ;
cin >> n;
cout << "1 到 " << n << " 之间的素数为: ";
sieveOfEratosthenes(n);
return 0;
}筛法优化素因数分解
const int N = 1e7;
bool isPrime[N + 1];
int minFactor[N + 1];
void eratos(int n) {
int i, j;
isPrime[0] = isPrime[1] = false;
minFactor[0] = minFactor[1] = -1;
for (i = 2; i <= n; ++i) {
isPrime[i] = true;
minFactor[i] = i;
}
for (i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (j = i * i; j <= n; j += i) {
isPrime[j] = false;
if (minFactor[j] == j)
minFactor[j] = i;
}
}
}
}
vector<int>factor(int x) {
vector<int> ret;
while (x > 1) {
ret.push_back(minFactor[x]);
x /= minFactor[x];
}
return ret;
}
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
bool isPrime(int a) {
if (a < 2)
return false;
for (int i = 2; i * i <= a; i++) {
if (a % i == 0)
return false;
}
return true;
}
int main() {
int n;
while (cin >> n) {
vector<int> primes; // 分解质因数
for (int i = 2; i * i <= n; ++i) {
while (n % i == 0) {
primes.push_back(i);
n /= i;
}
} // 如果n是质数且大于2
if (n > 2)
primes.push_back(n); // 打印质因数
cout << "Prime factors: ";
for (int prime : primes) {
cout << prime << " ";
}
cout
<< endl; // 如果需要计算质因数的乘积（通常这将是原始数n，除非有重复因子被忽略）
long long product = 1;
for (int prime : primes) {
product *= prime;
}
}
return 0;
}
-
isPrime函数- 目的：用于判断一个整数是否为质数。
- 逻辑：如果数字小于 2 则不是质数。然后从 2 开始到该数的平方根进行遍历，如果能被整除则不是质数，否则是质数。
-
main函数- 输入部分：通过
while (cin >> n)不断获取用户输入的整数n。 - 分解质因数部分：
- 使用一个循环从 2 到
n的平方根，找到能整除n的数i，将其添加到primes向量中，并不断更新n的值。 - 如果最后
n仍然大于 2，说明n本身也是一个质因数，将其添加到primes中。
- 使用一个循环从 2 到
- 输出部分：
- 首先输出质因数，通过遍历
primes向量并打印每个质因数。 - 然后计算质因数的乘积，通过遍历
primes向量并累乘每个质因数。
- 首先输出质因数，通过遍历
- 输入部分：通过
欧拉筛法（线性筛）
- 基本思路：通过维护每个数的最小质因数来筛选素数。对于每个数，只通过其最小质因数来筛去合数。
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1000005;
vector<int> primes;
bool isNotPrime[MAXN];
void EulerSieve(int n) {
for (int i = 2; i <= n; ++i) {
if (!isNotPrime[i]) {
primes.push_back(i);
}
for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
isNotPrime[i * primes[j]] = true;
if (i % primes[j] == 0) {
break;
}
}
}
}
int main() {
int n;
while (cin >> n) {
EulerSieve(n);
cout << "小于等于 " << n << " 的质数有: " << endl;
for (int prime : primes) {
cout << prime << " ";
}
cout << std::endl;
primes.clear(); // 每次输入新的 n 之前清空 primes 向量，避免结果累加
}
return 0;
}
-
EulerSieve函数- 这个函数的目的是使用欧拉筛法找出小于等于给定值
n的所有质数。 - 外层的
for循环从 2 遍历到n。 - 如果当前数字
i未被标记为非质数（isNotPrime[i]为false），则将其添加到primes向量中，因为它是一个质数。 - 内层的
for循环用于标记当前数字i与已找到的质数的乘积为非质数。但如果i能被当前的质数整除，就通过break退出内层循环，这是为了保证每个合数只被其最小质因数筛掉。
- 这个函数的目的是使用欧拉筛法找出小于等于给定值
-
main函数- 首先定义了一个整数
n用于接收用户输入。 - 通过
while (cin >> n)不断获取用户输入的数字。 - 每次输入新的
n后，调用EulerSieve函数进行质数的筛选。 - 然后输出小于等于
n的所有质数，并在输出前添加提示信息，且换行。 - 最后通过
primes.clear()清空primes向量，为下一次输入和筛选做好准备。
- 首先定义了一个整数
前n个数的约数之和
#include <iostream>
using namespace std;
// 计算一个数的约数之和
int sumOfDivisors(int num) {
int sum = 0;
for (int i = 1; i * i <= num; i++) {
if (num % i == 0) {
sum += i;
if (i != num / i) {
sum += num / i;
}
}
}
return sum;
}
// 计算前 n 个数的约数之和
int sumOfDivisorsForFirstN(int n) {
int totalSum = 0;
for (int i = 1; i <= n; i++) {
totalSum += sumOfDivisors(i);
}
return totalSum;
}
int main() {
int n;
while (cin >> n) {
int result = sumOfDivisorsForFirstN(n);
cout << "前 " << n << " 个数的约数之和为: " << result << endl;
}
return 0;
}
-
sumOfDivisors函数- 从 1 到该数的平方根进行遍历。
- 如果
num能被i整除，就将i加到和中。 - 如果
i不等于num / i（即i和num / i是不同的约数），则将num / i也加到和中。
-
sumOfDivisorsForFirstN函数- 通过一个循环从 1 到
n，对每个数调用sumOfDivisors函数计算其约数之和，并累加到totalSum中。
- 通过一个循环从 1 到
BZOJ1053——反素数
反素数（又称逆素数）是指一个正整数满足：对于任意小于它的正整数，其约数个数都小于该数的约数个数。
[HAOI2007]反素数ant - 题目详情 - BZOJ by HydroOJ
#include <iostream>
#include <cmath>
using namespace std;
const int N = 1e5 + 5;
int n, cntp, pri[N], vis[N], ans, mx;
void dfs(int i, int cur, int cnt) {
if (cnt > mx) {
mx = cnt;
ans = cur;
}
else if (cnt == mx) {
ans = min(ans, cur);
}
if (i > min(10, cntp)) {
return;
}
dfs(i + 1, cur, cnt);
int num = pri[i];
for (int j = 1; 1LL * cur * num <= n; j++) {
cur *= num;
dfs(i + 1, cur, cnt * (j + 1));
}
}
int main() {
cin >> n;
int k = sqrt(n);
for (int i = 2; i <= k; i++) {
if (!vis[i]) {
pri[++cntp] = i;
}
for (int j = 1; pri[j] * i <= k; j++) {
vis[pri[j] * i] = 1;
if (i % pri[j] == 0) {
break;
}
}
}
dfs(1, 1, 1);
cout << ans << endl;
return 0;
}首先，定义了一些常量和变量，包括问题规模 N ，整数 n ，质数数量 cntp ，质数数组 pri ，标记数组 vis ，最终答案 ans 以及最大值 mx
在 dfs 函数中：
- 首先判断当前的计数
cnt是否大于最大值mx，如果是则更新mx和ans；如果cnt等于mx，则更新ans为更小的值。 - 接着，如果当前的搜索层数
i超过了限制（min(10, cntp)），则返回不再继续搜索。 - 然后进行两种情况的搜索：
- 不选择当前层的质数，直接递归到下一层。
- 选择当前层的质数，通过一个循环不断乘以当前质数，更新当前数值
cur和计数cnt，并递归到下一层。
在 main 函数中：
- 首先读取输入的整数
n。 - 然后通过两层循环来找出小于等于
sqrt(n)的质数，并存储在pri数组中，同时标记相应的合数。 - 最后调用
dfs函数进行深度优先搜索，并输出最终的答案ans。
最大公约数
高精度数的二进制求gcd（a,b)
int gcd(int m, int n) {
if (m == n)
return m;
if (m < n)
return gcd(n, m);
if (m & 1 == 0)
return (n & 1 == 0) ? 2 * gcd(m >> 1, n >> 1) : gcd(m >> 1, n);
return (n & 1 == 0) ? gcd(m, n >> 1) : gcd(n, m - n);
}