codevs——1436 孪生素数 2-白红宇

codevs——1436 孪生素数 2

阅读量：5858 次

发布时间：2019-06-19

本文共 1579 字，大约阅读时间需要 5 分钟。

1436 孪生素数 2

时间限制: 2 s

空间限制: 1000 KB

题目等级 : 白银 Silver

题目描述

Description

如m=100,n=6

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

5　11

7　13

....

83　89

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

输入描述

Input Description

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

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

输出描述

Output Description

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

样例输入

Sample Input

例如１：

50　2

例如２：

100 90

例如３：

200　199

样例输出

Sample Output

例如１：

3 5

5 7

11 13

17 19

29 31

41 43

Total Is:6

例如２：

7 97

Total Is:1

例如３：

Total Is:0

数据范围及提示

Data Size & Hint

m<=5000

思路：淼。。。。。

代码：

#include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define N 6000using namespace std;bool not_prime[N];int n,m,ans,sum,tot,prime[N];int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1; ch=getchar();}    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}void Euler_sieve(){    memset(not_prime,0,sizeof(not_prime));        for(int i=2;i<=n;i++)    {        if(!not_prime[i]) prime[++tot]=i;        for(int j=1;j<=tot;j++)        {            if(i*prime[j]>n) break;            not_prime[i*prime[j]]=1;            if(i%prime[j]==0) break;            }        }  }int main(){    n=read(),m=read();    Euler_sieve();not_prime[1]=1;    for(int i=1;i<=n-m;i++)      if(!not_prime[i]&&!not_prime[i+m])       printf("%d %d\n",i,i+m),sum++;    printf("Total Is:%d",sum);    return 0;}