文档介绍：数论初步:
一,整除与因式分解:
1,算术基本定理: n =a1^r1*a2^r2*a3^r3……
2,求素数:(试除法,筛选法):
素数测试
Ø费马小定理:若p为素数,则对于任意小于
p的正整数a,有a(p-1)≡1(mod p)
Ø证明:用欧拉定理直接得出
Ø二次探测定理:若p为素数,a2≡1(mod p)
小于p的正整数解只有1和p-1
Ø满足费马小定理和二次探测定理的数可以确定是素数
Miller-Rabin算法
Ø算法步骤:
Ø判定n是否为素数
Ø令n-1=m*2j,m为奇数
Ø随机在2到(n-1)之间取一个整数b
Ø令v=bm,之后每次对v平方,当v=1时,若上一次的v既
不是1也不是(n-1),由二次探测定理,n不是素数,退出;
不断循环直到计算出b(n-1)
Øv=1,满足费马小定理,通过测试;否则n一定不是素数
Ø选取几个不同的b多次测试
Miller-Rabin只能算一种测试,因为通过
测试的数不一定是素数,非素数通过测试
的概率是1/4
Ø虽然一次测试的结果不一定令人满意,但
五六次随机测试基本可以保证正确率超
%
For (int i = 2; i < n ;i++)
{
For (int j = 2,flay = 1; j < sqrt (n); j++)
If (I % j == 0)
{
Printf (“i不是素数”);
flay = 0;
}
Printf (“I 是素数”);
}
3 ,
int m = sqrt (n+);
int c = 0;
memset (vis,0,sizeof (vis));
for (int i = 2; i < = m; i++)
if (!vis[i])
{
prime[c++] = i;
for (int j = i*i; j <= n; j+= i) vis[j] = 1;
}
4,
int isprime[N];
t;
int isok (int x)
{
for(int i = 0; i < cnt && isprime[i] * isprime[i] <= x; i++)
if (x % isprime[i] == 0) return 0;
return 1;
}
void getprime ()
{
isprime[0] = 2;
isprime[1] = 3;
cnt = 2;
for (int i = 5; i < maxn; i++)
if (isok (i))
t++] = i;
}
5,因式分解:
int Factor (int num)
{
int m = 0;
for (int i = 0; i < cnt && isprime[i]*isprime[i] <= num; i++)
{
if (num%isprime[i] == 0)
{
arr[++m] = isprime[i];
r[m] = 0;
while (num % isprime[i] == 0 && num)
{
r[m]++;
num/= isprime[i];
}
}
}
if (num > 1)
{
arr[++m] = num;
r[m] = 1;
}
return m;
}
6,求约数:
void dfs (int now,int q,int m,int a,int b)
{
if (flay) return ;
if (q > a) return ;
if (now == m+1)
{
q 就是约数…..
return ;
}
for (int i = 0,t = 1;i <= r[now];i++,t*=arr[now])
{
dfs (now+1,q*t,m,a,b);
}
}
例题分析:
Fzu上的题:(.cn)
求一个数的真因子个数(不包括本身)。
n = p1^a1*p2^a2...pn^an.
那么真因子的个数就为:(a1+1)*(a2+1)...(an+1)-1;
求n的所有真因子的和。
由n = p1^a1*p2^a2...pr^ar.
再由生成函数得(1+p1+p1^2...+p1^a1)*(1+p2+p2^2...+p2^a2)...(1+pr+pr^2...pr^ar).
求最小公倍数为M的至少两个数的最小和。
m = p1^a1*p2^a2...pn^an.
当m = 1时:sum =