模运算-素数-计算方法

模运算举例：

  62⁶⁵ % 133
  = 62 * 62⁶⁴ % 133
  = 62 * (62²)³² % 133
  = 62 * 3844³² % 133
  = 62 * (3844 % 133)³² % 133
  = 62 * 120³² % 133

  = 62 * 36¹⁶ % 133
  = 62 * 99⁸ % 133
  = 62 * 92⁴ % 133
  = 62 * 85² % 133
  = 62 * 43 % 133
  = 2666 % 133
  = 6

HDU-2035代码：

#include<stdio.h>
int head;
int pan(int x,int y)
{if(y==0)return 1;if(y==1)return x%1000;if(y%2!=0)head=head*x%1000;return pan(x*x%1000,y/2);
}
int main()
{int  m,n,s;while(scanf("%d%d",&m,&n)&&(m||n)){head=1;s=pan(m,n);printf("%d\n",s*head%1000);}return 0;
}

至今还未发现什么高级点的素数计算方法。现在最常用的也就是筛选法，不过效率太低，数组一大就不适应了。

筛选法：就是标记数组中可以被2整除的，然后标记可以被3整除的，一直标记到可以n整除的，没被标记的就是素数。

HDU OJ 1262 代码

#include<stdio.h>
int main()
{int s[10001];int i,n,j;for(i=0;i<10001;i++)s[i]=1;for(i=2;i<=10000;i++){if(s[i]==1){for(j=2;j<i;j++){if(i!=j&&i%j==0){s[i]=0;break;}}}}while(scanf("%d",&n)&&n){int leap=0;for(i=(n-1)/2;i>=2;i--){if(s[i]==1&&s[n-i]==1)leap++;}printf("%d\n",leap);}return 0;
}