判断数字是否质数
bool isPrime(int x) { if (x < 2) { return false; } for (int i = 2; i <= x / i; i++) { if (x % i == 0) { return false; } } return true; }
https://en.wikipedia.org/wiki/Miller–Rabin_primality_test
https://www.luogu.com.cn/problem/P1217
因为 151 既是一个质数又是一个回文数(从左到右和从右到左是看一样的),所以 151 是回文质数。
写一个程序来找出范围 ( 一亿)间的所有回文质数。
第 1 行: 二个整数 a 和 b .
输出一个回文质数的列表,一行一个。
5 500
5
7
11
101
131
151
181
191
313
353
373
383
Hint 1: Generate the palindromes and see if they are prime.
提示 1: 找出所有的回文数再判断它们是不是质数(素数).
Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below.
提示 2: 要产生正确的回文数,你可能需要几个像下面这样的循环。
题目翻译来自NOCOW。
USACO Training Section 1.5
产生长度为5的回文数:
for (d1 = 1; d1 <= 9; d1+=2) { // 只有奇数才会是素数 for (d2 = 0; d2 <= 9; d2++) { for (d3 = 0; d3 <= 9; d3++) { palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...) } } }
#include <bits/stdc++.h> using namespace std; bool Prime(int x) { if (x < 2) { return false; } for (int i = 2; i * i <= x; i++) { if (x % i == 0) { return false; } } return true; } int z[100000], zc; int main() { for (int i = 1; i <= 10000; i++) { { char s[20] = {}; sprintf(s, "%d", i); int l = strlen(s); for (int i = 0; i < l; i++) { s[2 * l - 2 - i] = s[i]; } int x; sscanf(s, "%d", &x); if (Prime(x)) { z[zc++] = x; } } { char s[20] = {}; sprintf(s, "%d", i); int l = strlen(s); for (int i = 0; i < l; i++) { s[2 * l - 1 - i] = s[i]; } int x; sscanf(s, "%d", &x); if (Prime(x)) { z[zc++] = x; } } } sort(z, z + zc); int l, r; scanf("%d%d", &l, &r); for (int i = 0; i < zc; i++) { if (l <= z[i] && z[i] <= r) { printf("%d\n", z[i]); } } return 0; }
https://www.luogu.com.cn/problem/P1218
农民约翰的母牛总是产生最好的肋骨。你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。
农民约翰确定他卖给买方的是真正的质数肋骨,是因为从右边开始切下肋骨,每次还剩下的肋骨上的数字都组成一个质数。
举例来说: 全部肋骨上的数字 是质数;三根肋骨 是质数;二根肋骨 是质数;当然,最后一根肋骨 也是质数。 被叫做长度 的特殊质数。
写一个程序对给定的肋骨的数目 ,求出所有的特殊质数。 不是质数。
一行一个正整数 。
按顺序输出长度为 的特殊质数,每行一个。
4
2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393
【数据范围】
对于 的数据,。
题目翻译来自NOCOW。
USACO Training Section 1.5
#include <bits/stdc++.h> using namespace std; bool isPrime(int x) { for (int i = 2; i * i <= x; i++) { if (x % i == 0) { return false; } } return true; } int main() { int n; vector<int> a; a.push_back(2); a.push_back(3); a.push_back(5); a.push_back(7); cin >> n; vector<int> b; for (int i = 1; i < n; i++) { for (int i: a) { for (int j = 1; j < 10; j += 2) { if (isPrime(10 * i + j)) { b.push_back(10 * i + j); } } } a.swap(b); b.clear(); } for (int i: a) { printf("%d\n", i); } return 0; }
https://codeforces.com/problemset/problem/1178/D
https://www.luogu.com.cn/problem/CF1178D
连成一个环,加几条弦
https://codeforces.com/problemset/problem/1176/D
https://www.luogu.com.cn/problem/CF1176D
#include <bits/stdc++.h> using namespace std; const int N = 2750131; int v[N + 1]; int p[N + 1], pc; int n, x; int c[N + 1]; int main() { for (int i = 2; i <= N; i++) { if (!v[i]) { p[++pc] = i; } for (int j = 1; j <= pc && i * p[j] <= N; j++) { v[i * p[j]] = p[j]; if (v[i] == p[j]) { break; } } } cin >> n; for (int i = 0; i < 2 * n; i++) { cin >> x; c[x]++; } for (int i = N; i > 0; i--) { if (v[i]) { for (;c[i] > 0; c[i]--) { printf("%d ", i); c[i / v[i]]--; } } } for (int i = 1; i <= N; i++) { for (;c[i] > 0; c[i]--) { printf("%d ", i); c[p[i]]--; } } printf("\n"); return 0; }