2019-01-23-PAT乙级-1007-素数对猜想

2019-01-23-PAT乙级-1007-素数对猜想

2019-01-23-PAT乙级-1007-素数对猜想

原文链接:1007 素数对猜想

github代码地址:HibisciDai/OJ-PAT-ACM

2019-01-23-PAT乙级-1007-素数对猜想

编程描述

让我们定义 $d_{n}$ 为:$d_{n}$ = $p_{n+1}$ − $p_{n}$,其中 $p_{i}$ 是第 i 个素数。显然有 $d_{1}$ = 1,且对于 n > 1 有 $d_{n}$ 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

现给定任意正整数N(< $10^{5}$ ),请计算不超过N的满足猜想的素数对的个数。

辅助描述

1
2
3
4
5
作者: CHEN, Yue
单位: 浙江大学
时间限制: 200 ms
内存限制: 64 MB
代码长度限制: 16 KB

输入格式

输入在一行给出正整数N

输出格式

在一行中输出不超过N的满足猜想的素数对的个数。

输入样例

1
20

输出样例

1
4

算法实现

算法分析

$p_{1}$ = 1
$p_{2}$ = 2
$p_{3}$ = 3
$p_{4}$ = 5
$p_{5}$ = 7
$p_{6}$ = 11
$p_{7}$ = 13
$p_{8}$ = 17
$p_{9}$ = 19
$p_{10}$ = 23

$d_{1}$ = $p_{2}$ - $p_{1}$ = 1
$d_{2}$ = $p_{3}$ - $p_{2}$ = 1
$d_{3}$ = $p_{4}$ - $p_{3}$ = 2
$d_{4}$ = $p_{5}$ - $p_{4}$ = 2
$d_{5}$ = $p_{6}$ - $p_{5}$ = 4
$d_{6}$ = $p_{7}$ - $p_{6}$ = 2
$d_{7}$ = $p_{8}$ - $p_{7}$ = 2

只要判断相邻两个数为素数即可

JAVA(openjdk)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.Scanner;

public class Main {
public static Scanner sc = new Scanner(System.in);

public static boolean isPrime(int n) {
if (n == 1 || n == 0)
return false;
if (n == 2)
return true;

int temp = (int) Math.sqrt((double) n);

for (int i = 2; i <= temp; i++)
if (n % i == 0)
return false;

return true;
}

public static void main(String[] args) {
int N = sc.nextInt();
sc.close();
int out = 0;//满足条件的素数

for (int i = 3; i <= N - 2; i++) {
if (isPrime(i) && isPrime(i + 2))
out++;
}
System.out.println(out);
}
}

运行结果

1
2
3
4
5
6
7
8
9
状态	分数	题目	编译器	耗时	用户
答案正确 20 1007 Java (openjdk) 178 ms HibisciDai
测试点 结果 耗时 内存
0 答案正确 132 ms 11388 KB
1 答案正确 150 ms 11412 KB
2 答案正确 151 ms 11192 KB
3 答案正确 148 ms 11452 KB
4 答案正确 133 ms 11400 KB
5 答案正确 178 ms 11448 KB

C

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cmath>
#include<iostream>
using namespace std;

bool isPrime(int n)
{
if(n==1 ||n==0)
return false;
if(n==2)
return true;

int tmp =(int)sqrt((double)n);

for(int i = 2;i<=tmp;i++)
if(n%i==0)
return false;

return true;
}
int main()
{
int num,count=0;
cin>>num;
for(int i = 3;i<=num-2;i++)
{
if(isPrime(i)&&isPrime(i+2))
count++;
}
cout<<count<<endl;
system("pause");
}

运行结果

1
2
3
4
5
6
7
8
9
状态	分数	题目	编译器	耗时	用户	
答案正确 20 1007 C++ (g++) 18 ms HibisciDai
测试点 结果 耗时 内存
0 答案正确 5 ms 640 KB
1 答案正确 9 ms 532 KB
2 答案正确 5 ms 640 KB
3 答案正确 4 ms 640 KB
4 答案正确 4 ms 384 KB
5 答案正确 18 ms 512 KB
文章作者: HibisciDai
文章链接: http://hibiscidai.com/2019/01/23/2019-01-23-PAT乙级-1007-素数对猜想/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 HibisciDai