205

20

4

• 在质数表的可判断范围内
• 不超过输入的n

# 代码

## C++解法

#include <cstring>
#include <iostream>
using namespace std;

const int maxn = 1e5 + 5;

int prime[maxn];
bool isPrime[maxn];
int pos;

void listPrime(int maxNum) {
memset(isPrime, true, sizeof(isPrime));
isPrime[0] = isPrime[1] = false;
pos = 0;
for (int i = 2; i <= maxNum; ++i) {
if (isPrime[i])
prime[pos++] = i;
for (int j = 0; j < pos && i * prime[j] <= maxNum; ++j) {
isPrime[i * prime[j]] = false;
if (!(i % prime[j]))
break;
}
}
}

int ans[maxn];
int main() {
cin.tie(0);
cin.sync_with_stdio(false);

int n;
cin >> n;
listPrime(n);

int cnt = 0;
for (int i = 1; prime[i] <= n && i < pos; ++i) {
if (prime[i] - prime[i - 1] == 2)
cnt++;
}
cout << cnt << endl;
return 0;
}

## Python解法

def listPrime(MAX):
isPrime = [True for i in range(MAX + 1)]
isPrime[0] = isPrime[1] = False
prime = []
for i in range(2, MAX + 1):
if isPrime[i]:
prime.append(i)
for j in range(0, len(prime)):
if i * prime[j] > MAX:
break
isPrime[i * prime[j]] = False
if not (i % prime[j]):
break
return prime

n = int(input())
prime = listPrime(n)

cnt = 0
i = 1
while 1:
if i >= len(prime) or prime[i] > n:
break
if prime[i] - prime[i - 1] == 2:
cnt += 1
i += 1
print(cnt)


## Java解法

import java.lang.reflect.Array;
import java.util.*;

class Main {

public static final int maxn = 100005;
public static int[] prime = new int[maxn];
public static boolean[] isPrime = new boolean[maxn];
public static int pos;

public static void listPrime(int maxNum) {
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
pos = 0;

for (int i = 2; i <= maxNum; ++i) {
if (isPrime[i])
prime[pos++] = i;
for (int j = 0; j < pos && i * prime[j] <= maxNum; ++j) {
isPrime[i * prime[j]] = false;
if (i % prime[j] == 0)
break;
}
}
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
listPrime(n);
int cnt = 0;
for (int i = 1; i < pos && prime[i] <= n; ++i) {
if (prime[i] - prime[i - 1] == 2)
cnt++;
}
System.out.println(cnt);
in.close();
}

}

• 点击查看/关闭被识别为广告的评论