Prime Twins |
||
| [ Submit Code ] [ Top 20 Runs ] [ Runs Status ] | ||
| Acceteped : 2041 | Submit : 6022 | |
| Time Limit : 1000 MS | Memory Limit : 65536 KB | |
Description |
||
题目描述 如果n和n+2都是素数，我们称其为孪生素数，比如3和5，5和7都是孪生素数。 给你一个区间[a,b],请问期间有多少对孪生素数？ 输入 第一行是一个整数K(K≤ 10000)，表示样例的个数。 以后每行一个样例，为两个整数，a和b，1≤a≤b≤5000000。 输出 每行输出一个样例的结果。 样例输入 5 1 3 1 10 1 100 1 1000 1 5000000 样例输出 0 2 8 35 32463 |
||
思路分析：这道题主要就是要打表（标记素数，标记孪生素数，记录每个数前面到底有多少个孪生素数）
#include<stdio.h>
int arr[5000001] = { 0 };
//用来标记所有的孪生素数
int brr[5000001] = { 0 };
int main() {
//开始打表
//我们定义0是素数，1为非素数;
arr[0] = 1;
arr[1] = 1;
for (int i = 2; i <= 5000000; i++) {
if (arr[i] == 0) {//==0就代表没有被遍历过，就说明该数一定是素数
for (int j = 2 * i; j <= 5000000; j += i) {
arr[j] = 1;
}
}
}
//打表完成，已经标记了5000000中的所有素数
//记录每一个数字前面有多少个孪生素数;
for (int i = 2; i <5000001; i++) {
brr[i] += brr[i - 1];//记录前面的一个数的前面有多少个孪生素数并把其交给下一个数
if (arr[i] == 0 && arr[i + 2] == 0) {
brr[i+2]++;//如果3是素数，且5是素数，就代表5前面存在一个孪生素数。就++
}
}
int k;
scanf("%d", &k);
while (k--) {
int a, b;
int count = 0;
scanf("%d %d", &a, &b);
count = brr[ b] - brr[a+1];//这里用a+1能过，但a不能过，不知道为什么
printf("%d\n", count);
}
}
本文含有隐藏内容，请 开通VIP 后查看