1436 孪生素数 2

2018-06-17 22:45:03来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

1436 孪生素数 2

 

时间限制: 2 s
空间限制: 1000 KB
题目等级 : 白银 Silver
 
 
 
 
题目描述 Description

如m=100,n=6

则将输出100以内的所有相差6的孪生素数:如,

5 11

7 13

....

83 89

请按此规律输出数与数之间用半角空格区分,每一对一行.

输入描述 Input Description

第一行输入一个整数数m为一个范围(如100)

第二行输入一个整数k为目标孪生素数的公差(如6)

输出描述 Output Description

每行输出一对,最后一行输出:Total Is:?(?表示总共有几对这样的数,如果不存在则输出Total Is:0)

样例输入 Sample Input

例如1:

50 2

例如2:

100 90

例如3:

200 199

样例输出 Sample Output

例如1:

3 5
5 7
11 13
17 19
29 31
41 43
Total Is:6

例如2:

7 97
Total Is:1

例如3:

Total Is:0

数据范围及提示 Data Size & Hint

m<=5000

分类标签 Tags 点此展开

这道题应该有更优化的算法,但是我一看m<=5000 .....二话不说暴力!
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 const int MAXN=10000001;
 6 int vis[MAXN];
 7 int bc[MAXN];
 8 int now=1;
 9 int main()
10 {
11     int m,n;
12     scanf("%d%d",&m,&n);
13     for(int i=2;i<=sqrt(m);i++)
14     {
15         if(vis[i]==0)
16         {
17             for(int j=i*i;j<=m;j=j+i)
18             {
19                 vis[j]=1;
20             }
21         }
22     }
23     /*int pre=-1;
24     
25     for(int i=2;i<=m;i++)
26     {
27         if(vis[i]==0)
28         {
29             if(i-pre==n)
30             {
31                 printf("%d %d\n",pre,i);
32                 tot++;
33             }
34             pre=i;
35         }
36     }*/
37     int tot=0;
38     for(int i=2;i<=m;i++)
39     {
40         if(vis[i]==0)
41         {
42             bc[now]=i;
43             now++;
44         }
45     }
46     for(int i=1;i<=now-1;i++)
47     {
48         for(int j=1;j<=now-1;j++)
49         {
50             if(bc[j]-bc[i]==n)
51             {
52                 printf("%d %d\n",bc[i],bc[j]);
53                 tot++;
54             }
55         }
56     }
57     printf("Total Is:%d",tot);
58     return 0;
59 }
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 const int MAXN=10000001;
 6 int vis[MAXN];
 7 int bc[MAXN];
 8 int now=1;
 9 int main()
10 {
11     int m,n;
12     scanf("%d%d",&m,&n);
13     for(int i=2;i<=sqrt(m);i++)
14     {
15         if(vis[i]==0)
16         {
17             for(int j=i*i;j<=m;j=j+i)
18             {
19                 vis[j]=1;
20             }
21         }
22     }
23     /*int pre=-1;
24     
25     for(int i=2;i<=m;i++)
26     {
27         if(vis[i]==0)
28         {
29             if(i-pre==n)
30             {
31                 printf("%d %d\n",pre,i);
32                 tot++;
33             }
34             pre=i;
35         }
36     }*/
37     int tot=0;
38     for(int i=2;i<=m;i++)
39     {
40         if(vis[i]==0)
41         {
42             bc[now]=i;
43             now++;
44         }
45     }
46     for(int i=1;i<=now-1;i++)
47     {
48         for(int j=1;j<=now-1;j++)
49         {
50             if(bc[j]-bc[i]==n)
51             {
52                 printf("%d %d\n",bc[i],bc[j]);
53                 tot++;
54             }
55         }
56     }
57     printf("Total Is:%d",tot);
58     return 0;
59 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Leetcode: 1.Two Sum

下一篇:1702 素数判定 2