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

題目

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

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

輸入格式:

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

輸出格式:

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

輸入樣例:

輸出樣例:

解答

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

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，

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/27262.html

標籤：C++

上一篇：1.ffmpeg、ffplay、ffprobe命令使用

下一篇：C++17結構化系結