一、前言

#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
int main()
{
     long long i,j;
    int a[]={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};
    for(i=1;i<1000000000;i++)//1亿
    {
        int hit=0;
        int hit1=-1;
        int hit2=-1;
        for(j=0;j<30&&hit<=2;j++)
        {
            if(i%a[j]!=0)
            {
                hit++;
                if(hit==1)
                    hit1=j;
                else if(hit==2)
                    hit2=j;
                else
                    break;

            }
        }
        if(hit==2&&(hit1+1==hit2))
            cout<<i<<endl;
    }
    return 0;
}

老师给出的要求：

阅读下面程序，请回答如下问题：

问题1：这个程序要找的是符合什么条件的数？

问题2：这样的数存在么？符合这一条件的最小的数是什么？

问题3：在电脑上运行这一程序，你估计多长时间才能输出第一个结果？时间精确到分钟（电脑：单核CPU 4.0G Hz，内存和硬盘等资源充足）。

问题4：在多核电脑上如何提高这一程序的运行效率?

（注：该程序、用C#语言编写，但是只要有C语言基础完全没有阅读压力，如果对部分语句不懂请自行查询）

using System;

using System.Collections.Generic;

using System.Text;

namespace FindTheNumber

{
　　class Program
　　{
　　　　static void Main(string[] args)
　　　　{
int [] rg ={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};
　　　　　　for (Int64 i = 1; i < Int64.MaxValue; i++)
　　　　　　{
　　　　　　　　int hit = 0;
　　　　　　　　int hit1 = -1;
　　　　　　　　int hit2 = -1;
　　　　　　　　for (int j = 0; (j < rg.Length) && (hit <=2) ; j++)
　　　　　　　　{
　　　　　　　　　　if ((i % rg[j]) != 0)
　　　　　　　　　　{
　　　　　　　　　　　　hit++;
　　　　　　　　　　　　if (hit == 1)
　　　　　　　　　　　　{
　　　　　　　　　　　　　　hit1 = j;
　　　　　　　　　　　　}
　　　　　　　　　　　　else if (hit == 2)
　　　　　　　　　　　　{
　　　　　　　　　　　　　　hit2 = j;
　　　　　　　　　　　　}
　　　　　　　　　　　　else
　　　　　　　　　　　　　　break;
　　　　　　　　　　}

　　　　　　　　}
　　　　　　　　if ((hit == 2)&& (hit1+1==hit2))
　　　　　　　　{
　　　　　　　　　　Console.WriteLine("found {0}", i);
　　　　　　　　}
　　　　　　}
　　　　}
　　}
}

二、分析

自己第一次看到这个C#代码时候，就觉得C#继承了C及C++语言的特性。首先我看着别扭，我把它写成了c语言。

Int64相当于2^64次方，10^20次方，相当于10亿=10^10次方。

(1)当i=1

j=0     i%rg[0]=1%2=1   1!=0   hit++   hit=1    hit1=j=0;

j=1     i%rg[1]=1%3=1   1!=0   hit++   hit=2    hit1=j=1;

j=2     i%rg[2]=1%4=1   1!=0   hit++   hit=3    break跳出当前循环。判断是否符合条件，不符合

(2)当i=2

j=0     i%rg[0]=2%2=0   0==0   

j=1     i%rg[1]=2%3=2   2!=0   hit++   hit=1    hit1=j=1;

j=2     i%rg[2]=2%4=2   2!=0   hit++   hit=2    hit2=j=2;

j=3     i%rg[3]=2%5=2   2!=0   hit++   hit=3    break跳出当前循环。判断是否符合条件，不符合

（3）当i=3

j=0     i%rg[0]=3%2=1   1！=0   hit++   hit=1    hit1=j=0;

j=1     i%rg[1]=3%3=0   0==0   hit++   hit=2    hit2=j=1;

j=2     i%rg[2]=3%4=1   1!=0   hit++   hit=3    break跳出当前循环。判断是否符合条件，不符合

（4）当i=4

j=0     i%rg[0]=4%2=0   0==0  

j=1     i%rg[1]=4%3=1   1！=0   hit++   hit=1    hit1=j=1;

j=2     i%rg[2]=4%4=0   0==0 

j=3     i%rg[3]=4%5=4   4！=0   hit++   hit=2   hit2=j=3；

j=4     i%rg[3]=4%6=4   4！=0   hit++   hit=3   break跳出当前循环。判断是否符合条件，不符合

。。。。。。。

。。。。。。。。。

    从这儿看出来：条件是：最终要是hit==2&&hit1+1==hit2；相邻的两个数同时取余后！=0，就一定满足条件hit1+1==hit2

     只有当相邻的两个数是在最后出现，break，前面所有的数都能被整除，那么问题来了，相邻两个数一定是一个奇数和一个偶数。偶数可以拆分为之前的2*相关的数。也就是说，偶数可以用之前的两个数来表示。即不存在这样的数。

三、解答

Int64相当于2^64次方，10^20次方，相当于10亿=10^10次方。

问题1：这个程序要找的是符合什么条件的数？

答：这个程序要找的数，相邻两个数是质数的数。

问题2：这样的数存在么？符合这一条件的最小的数是什么？

答：这样的数不存在。

问题3：在电脑上运行这一程序，你估计多长时间才能输出第一个结果？时间精确到分钟（电脑：单核CPU 4.0G Hz，内存和硬盘等资源充足）。（我的电脑是四核，3，4GHz）

答：测试的数据是1亿，用时5.034秒。

测试的数据是10亿，用时51.160秒。（基本上是满足增大10倍，时间上也是增大10倍）

所以，我们可以考虑认为：当数据达到10^20时，5.034*10^11秒=839 000 0000分钟。

问题4：在多核电脑上如何提高这一程序的运行效率?

答：多核电脑中，提高每个核的运算效率。实施多线程的控制，把这些数均分到多段，一段一个核，在每一个核中计算每一段的这些数，把每一个核的运算结果输出，多线程控制输入，运算，控制。

附带一张转换成C语言的代码（用Codeblock测得时间）

#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
int main()
{
     long long i,j;
    int a[]={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};
    for(i=1;i<1000000000;i++)//1亿
    {
        int hit=0;
        int hit1=-1;
        int hit2=-1;
        for(j=0;j<30&&hit<=2;j++)
        {
            if(i%a[j]!=0)
            {
                hit++;
                if(hit==1)
                    hit1=j;
                else if(hit==2)
                    hit2=j;
                else
                    break;

            }
        }
        if(hit==2&&(hit1+1==hit2))
            cout<<i<<endl;
    }
    return 0;
}

四、总结

1、分析问题的方式从简单到难。

2、从逻辑上进行推理，变换逻辑思维解决问题。

3、自己需要学习的知识还有很多，自己会每天进步一点。