NYOJ 26 孪生素数问题

╰半橙微兮° 2022-08-25 05:13 128阅读 0赞

## 孪生素数问题 ##

时间限制： 3000 ms | 内存限制： 65535 KB

难度： 3

描述

写一个程序，找出给出素数范围内的所有孪生素数的组数。一般来说，孪生素数就是指两个素数距离为2，近的不能再近的相邻素数。有些童鞋一看到题就开始写程序，不仔细看题，咱们为了遏制一下读题不认真仔细的童鞋，规定，两个素数相邻为1的也成为孪生素数。

输入

第一行给出N(0<N<100)表示测试数据组数。  
接下来组测试数据给出m，表示找出m之前的所有孪生素数。  
(0<m<1000000)

输出

每组测试数据输出占一行，该行为m范围内所有孪生素数组数。

样例输入

1
    14

样例输出

思路：生成一张素数表，判断是否为素数的时候查表即可。

#include <stdio.h>
    
    #define N 1000000
    short a[1000000+1];
    int main()
    {
    	int m,n;
    	int i, j;
    	a[0] = a[1] = 1;
    	for (i=2; i*i<=N; i++)
    	{
    		if (a[i] == 0)
    		{
    			for(j=2; j*i<=N; j++)
    			{
    				a[j*i] = 1;
    			}
    		}
    	}
    	scanf("%d",&m);
    	while (m--)
    	{
    		int total;
    		scanf("%d",&n);
    		if (n <= 2)
    		{
    			total = 0;
    		}
    		else
    		{
    			total = 1;
    			for (i=3; i<=n; i+=2)
    			{
    				
    				if ( (a[i]==0) && (a[i-2] == 0))
    				{
    					total++;
    				}
    			}
    		}
    		printf("%d\n",total);
    	}
    	return 0;
    }

再来看一个比较优秀的代码。

#include<stdio.h>  
    short array[1000000];  
    int main()  
    {  
          
        int sum , i , j;  
        for(i = 2 ; i < 1000 ; i++)  
        {  
            if(array[i] == 0)  
            {  
                for(j = i + i; j < 1000000 ; j += i)  
                    array[j] = 1;  
            }  
        }  
        for(sum = 1 , i = 3 ; i < 1000000 ; i++)  
        {  
            if(array[i] == 0 && array[i + 2] == 0)  
            {  
                array[i] = array[i + 1] = sum;  
                sum ++;  
                i ++;  
                continue;  
            }  
            array[i] = sum;  
        }  
        scanf("%d" , &i);  
        while(i--)  
        {  
            scanf("%d" , &j);  
            printf("%d\n" , array[j]);  
        }  
      
        return 0;  
    }