Sift out 2, 3, 5… 2,3,5… 2,3,5… Multiples of PI, and then everything else is prime, like the number of primes in the interval. V I s[] vis[] vis[] indicates whether to sieve out, pr I me[] prime[] prime[].

int sieve(int x) {
	for (int i = 0; i <= x; i++)vis[i] = false;/ / initialization
	for (int i = 2; i * i <= x; i++)// Filter out non-prime numbers
		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++)// Count primes
		if(! vis[i]) prime[k++] = i;return k;// Return the number of primes in [1,x]
}
Copy the code

Hdu-1262 Finds pairs of prime numbers

Goldbach’s guess is a little bit familiar. Instead of trying to prove this, we want to find two prime numbers that add up to the even number by taking any even number from the set of numbers that can be represented in the programming language. If we do this, we can prove that the conjecture is true. Since there can be different pairs of prime numbers to represent the same even number, it is specifically required that the pair of prime numbers being sought be the one whose values are most similar. Input The Input is some even integers M(5

Enumeration determines prime numbers

#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(a) {
	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;
}
Copy the code

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

If two primes differ by 2, it is called a pair of twin primes, and the number of twin primes in the interval [1,n] is found. Sieve method prime number type table, then determine twin, with prefix and record.

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100005;
int n, vis[maxn], ans[maxn];
void sieve(a) {
	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(a) {
	sieve(a);while (cin >> n && n > 0) {
		cout << ans[n] << "\n";
	}
	return 0;
}
Copy the code

Original is not easy, please do not reprint (this is not rich visits add insult to injury) blogger home page: blog.csdn.net/qq_45034708 If the article is helpful to you, remember to focus on the likes collection ❤