1.用简单素数筛选法求N以内的素数。

void printPrime()
{
	int n;
	scanf("%d",&n);
	
	int i,j;
	for(i=2;i<=n;i++) //遍历2~N的所有数 
	{
		for(j=2;j<=i;j++)
		{
			if(i%j==0&&i!=j)  //不是素数，跳出循环 
				break;
			
			if(i%j==0&&i==j)
				printf("%d\n",i);
		}
	}
	
}

2.使用位操作压缩后的筛素数方法

#include <stdio.h> 
#include <memory.h>

int getPrime(int primes[],int max)
{
	int i,j,n;
	int flag[max/32+1];
	n=0;
	memset(flag,0,sizeof(flag));
	for(i=2;i<max;i++)
		if(!( (flag[i/32]>>(i%32))&1 ))//判断指定位上是0还是1 
		{
			primes[n++]=i;
			for(j=i;j<max;j +=i)
				flag[j/32] |=(1<<(j%32));//在指定位上置1 
		}
	return n;	
}

void PrintfArray(int primes[],int n)
{
	for(int i=0;i<n;i++)
		printf("%d ",primes[i]);
	
	putchar('\n');
}

int main()
{
	int i=1000;
	int primes[i/3+1]={0};
	
	int n=getPrime(primes,i);
	PrintfArray(primes,n);
}

3.数组中除了两个数字外,其它数字都出现了2次，找出这两个数字。

void FindTwoNotRepeatNumberInArray(int *a, int n, int *pN1, int *pN2)
{
	int i, j, temp;
    
	//计算这两个数的异或结果
	temp = 0;
	for (i = 0; i < n; i++)
		temp ^= a[i];
	
	// 找第一个为1的位
	for (j = 0; j < sizeof(int) * 8; j++)
		if (((temp >> j) & 1) == 1)
			break;
 
	// 第j位为1,说明这两个数字在第j位上是不相同的
	// 由此分组即可
	*pN1 = 0, *pN2 = 0;
	for (i = 0; i < n; i++)
		if (((a[i] >> j) & 1) == 0)
			*pN1 ^= a[i];
		else
			*pN2 ^= a[i];
}

4.给定一个包含n个整数的数组，除了一个数出现一次外，所有整数均出现三次，找出这个只出现一次的整数.

  思路：对于出现3次的整数，它的二进制每一位1出现的次数都是3次。将该位置为0，剩下的就是出现1次的数。

int singleNumber(int a[],int n)
{
	int ones=0;         //二进制1出现奇数次的位 
	int twos=0;         //二进制1出现偶数次的位 
	int threes=0;       //用来处理二进制1出现三次的位
	 
	for(int i=0;i<n;i++)
	{
		twos |=(ones&a[i]);	    //ones&a[i] 遍历到当前变量为止 二进制1出现偶数次的位  
			                    //将结果与twos异或 统计所有二进制1出现偶数次的位 
		
		ones ^=a[i];		   //将ones异或当前元素,结果为二进制1出现奇数次的位 
		
		threes =~(ones&twos);  //ones&twos 若某位为1，说明出现3次,取反 清除出现3次的位 
		
		twos &=threes;    //清除twos中出现3次的位 
		
		ones &=threes;	  //清除ones中出现3次的位 
	}
	
	return ones;
}

5.快速幂  假设我们要求a^b，那么其实b是可以拆成二进制的，该二进制数第i位的权为2^(i-1)，因此可以将a¹¹转化为算 a2^0*a2^1*a2^3，也就是a1*a2*a8

int pow(int a,int b) 
{
	int ans=1,base=a;
	while(b!=0)
	{
		if(b&1 !=0)		//最后一位为1 
			ans *=base;		
		
		base *=base;
		b>>=1;	
	}
	
	return ans;
}

6.输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1的数字有1,10,11和12，1一共出现了5次。

从一个5位的数字举例分析，先考虑其百位为1的情况。分3中情况讨论（方便起见,计前三位为a,后两位为b）

  • 百位数字取2~9，example:33298 易知后两位的取值范围为00~99,,共10*10=100种情况。a的前两位的取值为00~a/10,所以共有（a/10+1)*100,即3400种情况
  • 百位数字==1， example：33198 易知前两位的取值范围为0~33，但当前三位固定为331时，后两位只能取0~98，所以共有（a/10+1-1)*100+b+1
  • 百位数字==0   example：33098 注意相比较第一种情况少了100次，易知取值范围为（a/10)*100

进一步统一百位数不为1的表达式（即百位数>=2或者==0）：((a+8)/10)*100 

加8的原因:百位数大于等于2时，加8产生进位，此时（a+8)/10的值等于a/10+1的值，举例：a=332时，a+8=340，340/10=34.而332/10+1=34

有了以上的分析，就可以很容易的写出求去1~N中各个位上1出现的次数之和的代码

int NumberOf1Between1AndN(int n)
{ 
	int count = 0; 
	int a,b;
	for (long i = 1; i <= n; i *= 10)
	{ 
		a = n / i;
		b = n % i; 
		count += (a + 8) / 10 * i + ((a % 10 == 1) ? b + 1 : 0); 
	} 
	return count; 
}

7.求1+2+3+...+,要求不能使用乘除法、for、if、else、switch、case等关键字及条件判断语句(A?B:C)

//利用函数指针求解 
typedef unsigned int (*fun)(unsigned int);

unsigned int solution(unsigned int n)
{
	return 0;
}

unsigned int Sum(unsigned int n)
{
	static fun f[2]={solution,Sum};
	return n+f[!!n](n-1);
}

8.不使用加减乘除做加法

int Add(int num1,int num2) 
{
	int sum,carry;
	do
	{
		sum=num1^num2;   //实现相加
		carry=(num1 & num2) <<1;    //实现进位
		
		num1=sum;
		num2=carry;
	}while(num2 !=0);
	
	return num1;
}

9.数组A[N]中的元素为整数类型，请你设计一个较快的算法将其分为左右两部分，使左边均为奇数而右边均为偶数。 

void swap(int a[],int i,int j)
{
	int temp=a[i];
	a[i]=a[j];
	a[j]=temp;
}
void OddEvenPartition(int a[],int n)
{ 
	int i=0,j=0; 
	while (i < n && (a[i] & 1)==0) i++; 
	if (i==n) return; 
	swap(a, i++, j++);
	while (i<n)
	{ 
		if ((a[i] & 1) == 1) //是奇数 
		{ 
		
			swap(a, i, j++); 
		
		} 
	  i++; 
	} 
}