学步园

题意简述

              题目要求找出1到10000内数，有多少个素数组成的总数；比如3只有自己那就是3，比如41有2+3+5+7+11+13, 11+13+17,和41，那就是三个（加起来数是连续的素数）

算法分析

   主要还是考验如何高效快速的得到素数表.下来就是如何得到开始计算的下标和把所有相加可能得出来。我先用的是朴素的，思考部分加上一些很高效的算法

程序样例

unsigned short IsPrime(unsigned short num)
{
	register unsigned short i=2;
	while(i*i <= num)
	{
		if(num % i == 0)
			break;
		else
			++i;
	}
	if(i*i <= num)
		return 0;
	return 1;
}

int main()
{
	unsigned short i,j,k,counter,tnum,sum;
	unsigned short num[670];
	for(i=2,j=0;i<5000;++i)
	{
		if(IsPrime(i))
			num[++j]=i;
	}
	num[0]=j;
	printf("%u\n",sizeof(short));
	while(1)
	{
		scanf("%hu",&tnum);//between 2 and 10000
		if(tnum == 0)
			return 0;
		counter=0;
		if(tnum > 4999)
		{
			i=num[0];
			if(IsPrime(tnum))
				++counter;
		}
		else
		{
			for(i=1;i<num[0];++i)
			{
				if(num[i] == tnum)
					++counter;
				if(num[i] >= tnum)
				{
					--i;
					break;
				}
			}
		}
		for(k=i;k>0;--k)
		{
			for(j=i,sum=0;j>0;--j)
			{
				sum+=num[j];
				if(sum == tnum)
					++counter;
				if(sum >= tnum)
				{
					--i;
					break;
				}
			}
		}
		printf("%hu\n",counter);
	}

	return 0;
}

流程：

            先把5000内素数，存入数组中，期间算法就是用FOR+朴素的取余判断（效率不高）。下来找到比需要查询数小的数的下标。用来循环判断组成可能。

    NOTE:为什么是5000内呢，因为5000以上的数单独判断就行，要组成的话肯定是两个加和小于10000的组合，所以5000内就够用了

            下来就是两层循环，从刚才下标开始往前加，大了就从前一个重来。直到开始下标小于1

指标：

POJ评定  176K 16MS(诡异的是第一次没改前是0MS)

思考

朴素的判断素数确实效率不高，经大大指导 知道了快速点的方法

筛选法

  思路是，要求10000以内的所有素数，把1-10000这些数都列出来，1不是素数，划掉；2是素数，所有2的倍数都不是素数，划掉；取出下一个幸存的数，划掉它的所有倍数；直到所有幸存的数的倍数都被坏掉为止。完成了就可以直接用a[n]
== 1来判断素数了 效率确实很高

    int i, tmp;
    int a[10000]
    memset(a, 0, sizeof(a));
    a[0] = 1;
    a[1] = 1;
    for(i=2;i<10000;i++)
    {
        if(!a[i])
        {
            tmp = i*2;;
            while(tmp < 10000)
            {
                a[tmp] = 1;
                tmp += i;
            }
        }
    }

不过这样出来的素数数组是离散的 中间有很多0 算加和的话，不知道影响大不。但是总体上肯定比我写的效率高~