演算法筆記刷題7（PAT乙級1007素數猜想）

題目

讓我們定義dn為：dn=pn+1−pn，其中pi是第i個素數。顯然有d1=1，且對於n>1有dn是偶數。“素數對猜想”認為“存在無窮多對相鄰且差為2的素數”。

現給定任意正整數N(<105)，請計算不超過N的滿足猜想的素數對的個數。

輸入格式:

輸入在一行給出正整數N。

輸出格式:

在一行中輸出不超過N的滿足猜想的素數對的個數。

輸入樣例:

20

輸出樣例:

4

解答

看到這個題我是不屑一顧的，因為“看起來”就是很簡單啊！！！於是我飛快寫出了第一個版本：

1.0

思路很簡單：這種相差2的只可能是奇數啊，我從3開始把裡面的奇數都抓來看看是不是素數不就行了？（是我太天真了嗚嗚嗚）

#include <stdio.h>
int primeNum(int n);

int main()
{
    int n,count=0;
	scanf("%d",&n);
	if(n>4){
		for(int i=3;i+2<=n;i=i+2){
			int t;
			t=primeNum(i)*primeNum(i+2);
			if(t==0)count++;
		}
		
	}
	printf("%d",count);
	return 0;
}
int primeNum(int n){
	if(n==2)return 0;
	for(int i=2;i<n;i++){
		if(n%i==0)return 0;
	}
	return 0;
}

然後就到了大家喜聞樂見的丟人環節：

然後天真的我覺得要減少函數調用，眉頭一皺計上心來，搞出了1.5個版本

1.5

#include <stdio.h>
int primeNum(int n);

int main()
{
    int n,count=0;
	scanf("%d",&n);
	if(n>4){
		for(int i=3;i+2<=n;i=i+2){
			int t;
			t=primeNum(i);
			if(t==1)count++;
		}
		
	}
	printf("%d",count);
	return 0;
}
int primeNum(int n){
	int n1=n+2;
	for(int i=2;i<n;i++){
		if(n%i==0)return 0;
	}
	for(int i=2;i<n1;i++){
		if(n1%i==0)return 0;
	}
	return 1;
}

然後，然後就又超時了呢嗚嗚嗚？？？？？

開始查資料簡化：首先，判斷一個數n是不是素數，只需要判斷從2到根號n的區間內有沒有能整除它的。其次，我的素數判斷做了很多的重覆工作。比如判斷3，5，7三個數字時，我已經算出了3，5均為素數，到計算5，7時候又得算一次5。即除了首尾外多做了一遍無用功。

綜合，我寫出了2.0版本

2.0

如果能把從3開始的素數表打出來，再判斷前後兩個數字的間距是否為2，工作量會減少很多很多。

#include<stdio.h>
#include<math.h>
int a[100000];
int main()
{
    int n,t=0,k=0;
    scanf("%d",&n);
    for(int i=3;i<=n;i=i+2){
    	int j;
        for(j=2;j<=sqrt(i);j++){
            if(i%j==0)
                break;
        }
        if(j>sqrt(i))
            a[k++]=i;
    }
    for(int i=0;i<=n;i++){
        if(a[i+1]-a[i]==2){
            t++;
        }
    }
    printf("%d",t);
    return 0;
}

結果：

這個時間比較理想。因為如果不把素數表打出來，光改素數的判斷方式的話，最後一個點用時是31ms。