【PAT乙级】1007素数对猜想 C++实现

1.解题思路
我们先看一下素数的概念：

一个大于1的自然数，且除了1和它本身外，不能被其他自然数整数整除的数叫素数。素数有时也叫质数。

明确了素数概念之后，我们如何写程序来判断任意一个自然数n（n > 1）是素数呢？
方法一：由素数的概念可知，我们可以用n去除2到n-1的所有数，如果2到n-1里面的数，只要有一个能被n整除，那n就不是素数，只有这里面的所有数都不能n整除，才能说明n是素数。

void judge(int n){
  int j = 2;
  while(j 
注意：如果用第一种方法，将有一部分测试运行超时，因为第一种遍历的次数比较多。
 
方法二：
 自然数n的因数分成两大部分，一部分是小于n的平方根，另外一部分大于n的平方根，小于平方根和大于平方根的部分是一一对应的，因而可以只判断从2到平方根的数字是否都能被整除即可,这样可以有效减少循环的次数。这个属于程序的优化。
 
void judge(int n){
  int j = 2;
  int leng = (int)sqrt(n);
  while(j<=leng){
     if(n % j == 0) break;
     j++;
  }
  if(j > leng) cout << n << "是素数";
  else cout << n << "不是素数";
}
 
2.完整代码：
 
#include
#include
using namespace std;
int main(){
	int n;
    int k=-1,q,s=0;
    cin >> n;
	int a[n];
	for(int i = 2;i<=n;i++){
       int j = 2;
       int leng = (int)sqrt(i);
       while(j<=leng){
          if(i % j == 0) break;
          j++;
  }
      if(j > leng) 
			a[k++] = i; //将找到的素数存入数组a中
	}
	for(q=1;q<=k;q++){
		if(a[q]-a[q-1]==2){ //判断两个素数是否相差为2
			s++;  //计数满足猜想素数对的个数
		}
	}
	cout <