数论-素数

女爷i 2022-11-27 12:22 227阅读 0赞

### 文章目录 ###

*  判断素数
 *  筛法求素数
 *  例题
 *   *  HDU-1262
     *  HDU-3792

# 判断素数 #

--------------------

枚举 \[ 2 , x \] \[2,\\sqrt\{x\}\] \[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;
    }

# 筛法求素数 #

--------------------

依次筛掉 2 , 3 , 5... 2,3,5... 2,3,5...的倍数，然后剩下的数就是素数，比如求区间内素数个数。  
 v i s \[ \] vis\[\] vis\[\]表示是否被筛掉， p r i m e \[ \] prime\[\] prime\[\]存素数。

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 ##

[HDU-1262 寻找素数对][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 ][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][https_blog.csdn.net_qq_45034708]  
> *如果文章对你有帮助，记得关注点赞收藏❤*

[HDU-1262]: https://vjudge.net/problem/HDU-1262
[HDU-3792 Twin Prime Conjecture]: https://vjudge.net/problem/HDU-3792
[https_blog.csdn.net_qq_45034708]: https://blog.csdn.net/qq_45034708