当前位置:编程学习 > C/C++ >>

BNU1073:素数等差数列

你有没有听说过菲尔兹奖呢?让我们从这里说起吧。
菲尔兹奖是以已故的加拿大数学家、教育家J.C.菲尔兹的姓氏命名的,这是最著名的世界性数学奖项,因此也有人将菲尔兹奖誉为数学中的“诺贝尔奖”。第一次菲尔兹奖颁发于1936年,而后每4年一次。它是在每隔四年才召开一次的国际数学家大会上隆重颁发的,且每次获奖者仅2-4名,因此获奖的机会比诺贝尔奖还要少,获奖者是由国际数易做图合会从全世界的第一流青年数学家中评定、遴选出来的。他们都是数学天空中升起的灿烂明星,是数学界的精英。令人稍感遗憾的是,至今为止,还没有中国数学家获得菲尔兹奖。
不过,在历届菲尔兹奖得主中,我们还是可以看到华人的身影。1982年,美籍华裔丘成桐成为了第一个获得这项荣誉的华人数学家。在2006年的菲尔兹四位获奖者中,一个叫Terence Tao(陶哲轩)的华裔澳大利亚籍数学家备受瞩目。这个数学神童7岁进入高中,9岁进入大学,10岁、11岁、12岁参加国际数学奥林匹克竞赛分获铜牌、银牌、金牌,16岁获得学士学位,17岁获得硕士学位,21岁获得普林斯顿大学博士学位。他同时在数学的多个领域做出了卓越的成就。他杰出的数学天分,让世界为之震惊。
好像有些跑题了,现在言归正传。Terence Tao之所以能够获得菲尔兹奖,其主要成果之一是他成功证明了存在任意长的公差不为0的素数等差数列。这一命题的证明涉及了现代数论中的许多理论,极为复杂,这里我们只看一个由此产生的简单推论。显而易见,如果存在任意长的素数等差数列,那么,我们要寻找一定长的素数等差数列,必定能够寻找到无穷多个。
现在,我们只对长度为3的素数等差数列感兴趣。给出一个整数n,你能找出三个数大小都不超过n的所有长度为3的公差不为0的素数等差数列么?
 
Input
输入只有一个正整数n,n ≤ 10000。
Output
输出三个数大小都不超过n的所有长度为3的公差不为0的素数等差数列,每行按照从小到大的顺序输出数列中的三个数,两个数之间用空格间隔。对于多个不同的素数等差数列,先输出第一个数比较小的,第一个数相等的情况下先输出第二个数比较小的,依此类推。如果不存在这样的素数等差数列,请输出“No number sequence”。
Sample Input
11
Sample Output
3 5 7
3 7 11
 
 
 
题意:找出给出范围内所有三个素数的等差数列
 
 
#include <string.h>  
#include <algorithm>  
using namespace std;  
  
int prime[10005];  
int a[10005],len;  
  
void set()  
{  
    int i,j;  
    len = 1;  
    memset(prime,0,sizeof(prime));  
    for(i = 2;i<=10000;i++)  
    {  
        if(!prime[i])  
        {  
            for(j = i+i;j<=10000;j+=i)  
            {  
                prime[j] = 1;  
            }  
        }  
    }  
    a[0] = 2;  
    for(i = 3;i<10000;i+=2)  
    {  
        if(prime[i])  
        continue;  
        a[len++] = i;  
    }  
}  
  
int main()  
{  
    int i,j,k,n,x,y,z,d,l,cnt;  
    set();  
    while(~scanf("%d",&n))  
    {  
        cnt = 0;  
        for(i = 0;i<len;i++)  
        {  
            if(a[i]<=n)  
            l = i;  
            else  
            break;  
        }  
        for(i = 0;i<=l-2;i++)  
        {  
            x = a[i];  
            for(j = i+1;j<=l-1;j++)  
            {  
                y = a[j];  
                d = a[j]-a[i];  
                if(!prime[y+d] && y+d<=n)  
                {  
                    printf("%d %d %d\n",x,y,y+d);  
                    cnt++;  
                }  
            }  
        }  
        if(!cnt)  
        printf("No number sequence\n");  
    }  
  
    return 0;  
}  

 

 
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,