A - 寻找素数对
每个偶数都能找到两个素数，其相加等于该数
简单推一下比如 12 从中间 6 开始， 5 + 7 便是
再推几个就可以发现
只要从中间开始找，左右对称的第一个素数对便是要找的
所以我们抓到了关键点，需要 判断是否为素数 + 从中间开始往两边对称查找
注意如果中间的素数*2 就成立的话那也算
#include <cstdio>
const int N = 1e4 + 10;
bool st[N];
int prime[N], cnt;
int a[N];
int main()
{
int n;
for (int i = 2; i <= N; i++)
{
if (!st[i])
{
a[i] = i; // 查表
prime[cnt++] = i;
}
for (int j = 0; prime[j] * i <= N; j++) // 欧拉筛枚举素数
{
st[i * prime[j]] = true;
if (i % prime[j] == 0) break;
}
//printf("%d ", a[i]);
}
while (~scanf("%d", &n))
{
int t = n / 2;
while (t) // 从中间开始左右枚举
{
if (a[t])
if (a[n - t])
{
printf("%d %d\n", a[t], a[n - t]);
break;
}
t--;
}
}
}
B - 素数回文 HDU 1431
这题多考了个判断回文数
第一次做用的定义字符数组，将每位数存进去
然后双指针前后一起查找判断是否相等，结果超时了
后来查了别人博客发现可以直接定义一个int然后通过 b = b * 10 + (a % 10)
来直接得到逆序数字，之后判断一次相等就行
#include <cstdio>
const int N = 9989999;
bool st[N];
int prime[N], cnt;
int a[N];
bool iscircle(int x)
{
int b = 0;
int a = x;
while (a)
{
b = a % 10 + b * 10;
a /= 10;
}
if (x == b) return true;
return false;
}
void Euler()
{
for (int i = 2; i <= N; i++)
{
if (!st[i])
{
if (iscircle(i)) a[cnt] = i;
prime[cnt++] = i;
}
for (int j = 0; prime[j] * i <= N; j++)
{
st[i * prime[j]] = true;
if (i % prime[j] == 0) break;
}
}
}
int main()
{
Euler(); // 初始化 a 查询数组
int num1, num2;
while (~scanf("%d %d", &num1, &num2))
{
if (num2 >= 9989899) num2 = 9989899;
// 观察数据可以知道，最大就是这个
for (int i = 0; a[i] <= num2 && i <= 663960; i++)
{
//if (a[i] == 9989899)
// printf(" i = %d\n",i);
if (a[i] >= num1) printf("%d\n", a[i]);
}
printf("\n");
}
}
C - 分拆素数和 HDU 2098
水题，跟 A 一样做就行，不过是把输出变为 res++
不过这个题中两个素数不能相同
#include<cstdio>
const int N = 1e4 + 10;
bool st[N];
int primes[N], cnt;
int a[N];
void getprime()
{
for (int i = 2; i <= N; i++) {
if (!st[i]) {
a[i] = i;
primes[cnt++] = i;
}
for (int j = 0; primes[j] * i <= N; j++) {
st[i * primes[j]] = true;
if (i % primes[j] == 0) break;
}
}
}
int main() {
int n;
getprime();
while (~scanf("%d", &n) && n != 0) {
int t = n / 2;
int ans = 0;
while (t) {
if (a[t]) {
if (a[n - t]) {
if (a[t] != a[n - t])
ans++;
}
}
t--;
}
printf("%d\n", ans);
}
}
D - 素数判定 HDU 2012
唔
how waterful
#include<cstdio>
const int N = 1e6 + 10;
bool st[N];
int primes[N], cnt;
int a[N];
void getprime()
{
for (int i = 2; i <= N; i++) {
if (!st[i]) {
a[i] = i;
primes[cnt++] = i;
}
for (int j = 0; primes[j] * i <= N; j++) {
st[i * primes[j]] = true;
if (i % primes[j] == 0) break;
}
}
}
int main() {
int x, y;
getprime();
while (~scanf("%d%d", &x, &y) && (x || y)) {
bool flag = true;
for (int i = x; i <= y; i++)
{
int res = i * i + i + 41;
if (!a[res]) {
flag = false;
break;
}
}
if (flag) printf("OK\n");
else printf("Sorry\n");
}
E - Dertouzos HDU 5750
这题硬核一些
题目要求找到 从 1~ n 中 以 d 为最大因子的有几个
如
12 ： 1 2 3 4 6 12，最大因子为 6
9： 1 3 9 最大因子为 3
6：1 2 3 6 最大因子为 3
而我们已知的是最大因子 d，需要求出最大因子为 d 的数 a
那他跟 a 有啥关系？ 对，因子！
12 = 2 * 6
9 = 3 * 3
6 = 2 * 3
似乎有什么相似之处，都是与左边第一个非 1 因子相乘
而一个数左边的最开始的因子一定符合什么性质？ 是质数
诶，那我是不是用 d 跟素数表从小到大乘以便就能找出 所有以 d 为最大因子的数呢？
d = 4 时比如 3 * 4 = 12，也是跟素数相乘啊，但此时最大因子不再是 4，而是6
所以需要一个条件来约束，不能从头乘到尾
prime[i] % d != 0
总结一下
读入 d，用 d 跟素数表从小到大依次相乘，当碰到自己的因子时就停止
#include<cstdio>
#include <cstdlib>
const int N = 1e6 + 10;
bool st[N];
int primes[N], cnt;
//int a[N];
void getprime()
{
for (int i = 2; i <= N; i++) {
if (!st[i]) {
//a[i] = i;
primes[cnt++] = i;
}
for (int j = 0; primes[j] * i <= N; j++) {
st[i * primes[j]] = true;
if (i % primes[j] == 0) break;
}
}
}
int main() {
getprime();
int n, d;
int T;
scanf("%d", &T);
while (T--) {
int ans = 0;
scanf("%d%d", &n, &d);
for (int i = 0; i < cnt; i++) {
if (primes[i] * d > n) break; // 当大于 n 时超出范围结束
ans++;
if (d % primes[i] == 0) break; // 该结束了
}
printf("%d\n", ans);
}
return 0;
}
F - Prime Ring Problem HDU 1016
你以为是考素数？
是考我 DFS（深度优先搜索）哒！
没学咋办？学啊！
假设 n = 6， 则共有这几个数 1 2 3 4 5 6
从 1 开始，下一位 共可以放 2 3 4 5 6，但成立的只有 2 4 6
枚举时不成立的直接回溯
成立的就继续往下走
假设 1
选了 2， 那么当前序列 1 2， 可以选 3 4 5 6，成立的有 3 5
选了 3， 那么当前序列 1 2 3， 可以选 4 5 6， 成立的有 4
选了 4， 那么当前序列 1 2 3 4，可以选 5 6，成立的有 寄
回溯到 选 2
选了 5，那么当前序列 1 2 5， 可以选 3 4 6， 成立的有 6
选了 6， 那么当前序列 1 2 5 6，可以选 3 4， 成立的有 寄
回溯到起点
假设2
选 4， 那么当前序列 1 4，可以选 2 3 5 6， 成立的有 3
选 3， 那么当前序列 1 4 3，可以选 2 5 6， 成立的有 2
选 2， 那么当前序列 1 4 3 2， 可以选 5 6，成立的有 5
选 5， 那么当前序列 1 4 3 2 5，可以选 6，成立的有 6
选 6， 那么当前序列 1 4 3 2 5 6，到头，判断一下 1 + 6 是否为质数，成立
所以有一个正确答案 1 4 3 2 5 6
先贴一个dfs的模板，理解理解
// 输入一个数n，求出从1-n所有数的组合
// 输入 3
// 输出 123 132 213 231 312 321 （随便打的）
#include <cstdio>
const int N = 100020;
int path[N], u, n;
bool st[N];
void dfs(int u) {
if (u == n) { // 如果当前深搜层数到底，则输出当前路径的结果
for (int i = 0; i < n; i++) printf("%d ", path[i]);
printf("\n");
return;
}
for (int i = 1; i <= n; i++) { // 枚举每个可能项
if (!st[i]) {
// 如果当前项已被枚举过则跳过
path[u] = i;
// 当前路径层赋予结果
st[i] = true;
// 当前项已被枚举
dfs(u + 1);
// 下一层搜索
st[i] = false;
// 回溯，因为路径中每次都会重新赋值，所以不必回溯路径
}
}
}
int main() {
scanf("%d", &n);
dfs(0); // 从第0层深搜开始
return 0;
}
这个理解完了再看代码就很容易了
/*
Problem link : https://vjudge.net/problem/HDU-1016
Finish time : 2021/12/2 17:30 made by Aze
*/
#include <iostream>
#include <cstring>
const int N = 1e6 + 10;
bool st[N];
int primes[N], cnt;
int a[N]; // 前三行都是素数的东西
int path[N], n; // DFS
void getprime()
{
for (int i = 2; i <= N; i++) {
if (!st[i]) {
a[i] = i;
primes[cnt++] = i;
}
for (int j = 0; primes[j] * i <= N; j++) {
st[i * primes[j]] = true;
if (i % primes[j] == 0) break;
}
}
}
void dfs(int u, int num) {
if (u == n - 1 && a[path[u - 1] + 1]) { // 判断是否到达底层
printf("1 ");
for (int i = 0; i < n - 1; i++) {
printf("%d%c", path[i], i == n - 2 ? '\n' : ' ');
// 输出的行末不能有空格
}
}
for (int i = 2; i <= n; i++) { // 从2开始枚举
if (!st[i]) { // 如果没被枚举过就继续
if (a[num + i]) { //如果跟上一个数相加为素数
path[u] = i; // 放进结果里
st[i] = true; // 标记当前数已经被枚举过
dfs(u + 1, i);
st[i] = false;
}
}
}
}
int main() {
getprime();
cnt = 1;
memset(st, false, sizeof(st));
while (~scanf("%d", &n)) {
printf("Case %d:\n", cnt);
dfs(0, 1);
cnt++;
printf("\n");
}
return 0;
}
G - Goldbach's Conjecture HDU 1397
属于是英文版C题了
不过这次可以两个素数相同
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
bool st[N];
int prime[N], cnt;
int a[N];
void getprime() {
for (int i = 2; i <= N; i++) {
if (!st[i]) {
a[i] = i;
prime[cnt++] = i;
}
for (int j = 0; prime[j] * i <= N; j++) {
st[prime[j] * i] = true;
if (i % prime[j] == 0) break;
}
}
}
int main() {
int n;
getprime();
while (~scanf("%d", &n) && n) {
int res = 0;
int t = n / 2;
while (t) {
if (a[t]) {
if (a[n - t]) {
res++;
}
}
t--;
}
printf("%d\n", res);
}
}
H - Calling Extraterrestrial Intelligence Again HDU 1239
全是废话，建议从 In other words 开始看
输入数 m a b，其中 4 < m <= 1e5 1 <= a <= b <= 1000
找出两个素数 q p，满足 pq <= m，且 a / b <= p / q <= 1
输出满足条件的最大 q p
那就直接从m中间左右开找，全遍历
优化一下，从素数表里找
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int prime[N], cnt;
bool st[N];
void getprime() {
for (int i = 2; i <= N; i++) {
if (!st[i]) prime[cnt++] = i;
for (int j = 0; prime[j] * i <= N; j++) {
st[i * prime[j]] = true;
if (i % prime[j] == 0) break;
}
}
}
int find(int x) { // 二分找
int l = 0, r = cnt, mid;
while (l < r) {
mid = l + r >> 1;
if (prime[mid] >= x) r = mid;
else l = mid + 1;
}
return r;
}
int main() {
getprime();
int m, a, b;
while (~scanf("%d%d%d", &m, &a, &b) && m + a + b) {
int idx = find(m); // 找到小于等于m的最大素数
double c = (double)a / (double)b;
int p, q;
int max1 = -2e9;
for (int i = idx; i >= 0; i--)
for (int j = i; j <= idx; j++) {
if (prime[i] * prime[j] > m
|| (double)prime[i] / (double)prime[j] < c) break;
if (prime[i] * prime[j] > max1) {
max1 = prime[i] * prime[j];
p = i;
q = j;
}
}
printf("%d %d\n", prime[p], prime[q]);
}
}
I - Largest prime factor HDU 2136
找出一个数的最大素数因子，并输出它在素数表中的位置
比如 5 的最大素数因子 是 5， 5在素数表里位置为 3
12 的最大素数因子 为 3，位置为2
emmm，这题也好做，从 n 开始逆向遍历，判断第一个素数并且是它因子的就行
但感觉会TLE，在素数表里查应该也行
欧拉筛是碰到最小素因子就结束，
比如12，当枚举到6时，6 * 2 就结束了，枚举不到 3
但还有埃氏筛嘛，它会把是这个素因子的数全标记一遍，那么如果是后面的素数
也会重新把数标记一遍，直接替换掉原来的标记，这样最后得到的就是最大的了
还是12， 素数2会标记一次，3又会标记一次
代码如下：
#include <iostream>
const int N = 1e6 + 10;
int prime[N], cnt = 1; // 位置从 1 开始
bool st[N];
int a[N];
void getprime() {
a[1] = 0; // 特殊条件
for (int i = 2; i <= N; i++) {
if (!st[i]) {
a[i] = cnt; // 素数位置记录
prime[cnt] = i;
for (int j = i + i; j <= N; j += i) {
st[j] = true;
a[j] = cnt; // 这个数 的最大素因子（暂时）的位置在 cnt
}
cnt++;
}
}
}
int main() {
getprime();
int n;
while (~scanf("%d", &n)) {
printf("%d\n", a[n]);
}
}
J - How many prime numbers HDU 2138
休息休息
数据很大，不能查表
试除法搞定
不过边界条件别用 i * i <= n，会 WA，用 sqrt(n * 1.0)
#include <iostream>
#include <cmath>
const int N = 1e7;
bool isprime(int x) {
for (int i = 2; i <= (int)sqrt(x * 1.0); i++) {
if (x % i == 0) return false;
}
return true;
}
int main() {
int n;
while (~scanf("%d", &n)) {
int res = 0;
for (int i = 0; i < n; i++) {
int temp;
scanf("%d", &temp);
if (isprime(temp))
res++;
}
printf("%d\n", res);
}
}