学步园

算法思路来自网上笔试题答案。水平有限，有错的地方请指出。

要点: 循环最大值的选取. 去除一些明显不符合的数字(筛选法)

1. 求n以内的素数

void GetPrimer(int n)
{
	bool *isPrimer = new bool[n + 1];//从1开始.
	memset(isPrimer, true, n);

	isPrimer[1] = false;
	for(int i = 2; i < sqrt(n); i++)
	{
		if(isPrimer[i])
		{
			for(int j = i + i; j <= n; j+=i)
			{
				isPrimer[j] =  false;
			}
		}
	}

	int iPrintCount = 0;
	for(int k = 2; k <= n; k++)
	{
		if(isPrimer[k])
		{
			iPrintCount++;

			printf("%d ", k);

			if(iPrintCount % 20 == 0)
				printf("\n");
			
		}
	}

	printf("\nThe number of primers of %d is %d\n",n, iPrintCount);

	delete[] isPrimer;
}

这个求素数算效率高的。
注意: 这个筛选法。

2.前几天面试遇到的一个连续整数的题。

题目描述： 一个正整数有可能可以被表示为n(n>=2)个连续正整数之和，如：

15=1+2+3+4+5    15=4+5+6   15=7+8

请编写程序，根据输入的任何一个正整数，找出符合这种要求的所有连续正整数序列。

输入数据：一个正整数，以命令行参数的形式提供给程序。

输出数据：在标准输出上打印出符合题目描述的全部正整数序列，每行一个序列，每个序列都从该序列的最小正整数开始、以从小到大的顺序打印。如果结果有多个序列，按各序列的最小正整数的大小从小到大打印各序列。此外，序列不允许重复，序列内的整数用一个空格分隔。如果没有符合要求的序列，输出“NONE”。

例如，对于15，其输出结果是：1 2 3 4 5   4 5 6   7 8

对于16，其输出结果是：NONE

解题思路：  http://www.cnblogs.com/mervyn/archive/2010/06/15/1758673.html

最简单双重循环直接输出。

http://www.blogjava.net/qiyadeng/archive/2009/01/19/251913.html

效率稍微高点的解法。 n = a + (a+1) + (a+2)...+(a+k)=(a+a+k)(k+1)/2.

用了等差求和，得出一个最大值，k < (int)sqrt((double)n*2);

http://blog.csdn.net/duxingstar/article/details/6457220

这个利用了连续整数奇偶性质。效率算高的。

这个还需要好好研究下。。。

void getDivide(int n)
{
	if(n>2)
	{
		int temp=n;
		int num=0;
		int k,m;
		for(int i=3;i<=n/2;i++)
		{
			if(n%i==0)
			{
				k=(i-1)/2;
				m=n/i;
				for(int j=(m-k)>0?(m-k):(k-m+1);j<=(k+m);j++)
					cout<<j<<"+";
				cout<<endl;
			}
		}
		if(n%2==1)
			cout<<n/2<<"+"<<n/2+1;
		cout<<endl;

		while(temp!=0)
		{
			if(temp%2==0)
			temp=temp/2;
			else
				break;
			
		}
		if(temp==0)
				cout<<"NONE";
	}
	else
		cout<<"NONE";
}