数论-素数
数论-素数
文章目录
- 判断素数
- 筛法求素数
- 例题
- HDU-1262
- HDU-3792
判断素数
枚举 [2 ， x ]
bool prime(int x) {
if (x <= 1)return false;
for (int i = 2; i <= sqrt(x); i++)
if (x % i == 0)return false;
return true;
}筛法求素数
int sieve(int x) {
for (int i = 0; i <= x; i++)vis[i] = false;//初始化
for (int i = 2; i * i <= x; i++)//筛掉非素数
if (!vis[i])
for (int j = i * i; j <= x; j += i)
vis[j] = true;
int k = 0;
for (int i = 2; i <= x; i++)//统计素数
if (!vis[i])
prime[k++] = i;
return k;//返回[1,x]内素数个数
}例题
HDU-1262
Problem Description 哥德巴赫猜想大家都知道一点吧.我们现在不是想证明这个结论,而是想在程序语言内部能够表示的数集中,任意取出一个偶数,来寻找两个素数,使得其和等于该偶数. 做好了这件实事,就能说明这个猜想是成立的. 由于可以有不同的素数对来表示同一个偶数,所以专门要求所寻找的素数对是两个值最相近的. Input 输入中是一些偶整数M(5<M<=10000). Output 对于每个偶数,输出两个彼此最接近的素数,其和等于该偶数. Sample Input 20 30 40 Sample Output 7 13 13 17 17 23
枚举判断素数
#include<bits/stdc++.h>
using namespace std;
bool prime(int x) {
if (x <= 1)return false;
for (int i = 2; i <= sqrt(x); i++)
if (x % i == 0)return false;
return true;
}
int main() {
int m;
while (cin >> m) {
int a = m / 2;
if (a % 2 == 0)a--;
int b = m - a;
while (prime(a)==false||prime(b)==false) {
a -= 2;
b += 2;
}
cout << a << " " << b << "\n";
}
return 0;
}HDU-3792
HDU-3792 Twin Prime Conjecture
Problem Description If we define dn as: dn = pn+1-pn, where pi is the i-th prime. It is easy to see that d1 = 1 and dn=even for n>1. Twin Prime Conjecture states that “There are infinite consecutive primes differing by 2”. Now given any positive integer N (< 10^5), you are supposed to count the number of twin primes which are no greater than N. Input Your program must read test cases from standard input. The input file consists of several test cases. Each case occupies a line which contains one integer N. The input is finished by a negative N. Output For each test case, your program must output to standard output. Print in one line the number of twin primes which are no greater than N. Sample Input 1 5 20 -2 Sample Output 0 1 4
若两个素数相差2则称为一对孪生素数，求区间[1,n]内的孪生素数个数。 筛法素数打表，然后判断孪生，用前缀和记录。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100005;
int n, vis[maxn], ans[maxn];
void sieve() {
memset(vis, 0, sizeof(vis));
for (int i = 2; i * i <= maxn; i++)
if (!vis[i])
for (int j = i * i; j <= maxn; j += i)
vis[j] = 1;
ans[0] = ans[1] = 0;
vis[0] = vis[1] = 1;
for (int i = 2; i <= maxn; i++) {
ans[i] = ans[i - 1];
if (!vis[i] && !vis[i - 2])
ans[i]++;
}
}
int main() {
sieve();
while (cin >> n && n > 0) {
cout << ans[n] << "\n";
}
return 0;
}原创不易，请勿转载（
本不富裕的访问量雪上加霜） 博主首页：https://blog.csdn.net/qq_45034708