pat1007

普通方案：

#include<iostream>

#include<math.h>

using namespace std;

bool isPrime(int n);

int main(){

int cnt=0;

    int n;

    cin>>n;

for(int i=3;i+2<=n;i++)

if(isPrime(i)&&isPrime(i+2))

cnt++;

cout<<cnt;

system("pause");

return 0;

}

bool isPrime(int n){

for(int i=2;i<=sqrt(n);i++){

if(n%i==0)

return false;

}

return true;

}

image

空间换时间：

#include<iostream>

#include<math.h>

using namespace std;

bool isPrime(int n);

int main(){

int a[100001]={0};

int cnt=0;

    int n;

    cin>>n;

for(int i=2;i<=n;i++){

if(a[i]==0){

if(isPrime(i)){

for(int j=2;j*i<=n;j++)

a[j*i]=1;//标记非素数为1

}

else

a[i]=1;

}

}

for(int i=3;i+2<=n;i++)

if(a[i]==0&&a[i+2]==0)

//if(isPrime(i)&&isPrime(i+2))

cnt++;

cout<<cnt;

system("pause");

return 0;

}

bool isPrime(int n){

for(int i=2;i<=sqrt(n);i++){

if(n%i==0)

return false;

}

return true;

}

image

#include<iostream>
#include<math.h>
using namespace std;

bool isPrime(int n);

int main(){
    int a[100001]={0};
    int cnt=0;
    int n;
    cin>>n;
    for(int i=2;i<=n;i++){
        if(a[i]==0){
                if(isPrime(i)){
                    for(int j=2;j*i<=n;j++)
                    a[j*i]=1;//标记非素数为1即素数的倍数们都是非素数
                }
                else
                    a[i]=1;
        }
    }
    for(int i=3;i+2<=n;i++)
        if(a[i]==0&&a[i+2]==0)
            //if(isPrime(i)&&isPrime(i+2))
            cnt++;
    cout<<cnt;
    system("pause");
    return 0;
}

bool isPrime(int n){
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0)
            return false;
        else return true;//伪素数，导致尽可能多的标记非素数，同时减少判断是否是的运行时间（取模计算比赋值更费时间）
    }
}

图片.png