数论初步

GCD算法:

int gcd(int a,int b){ return b==0?a:gcd(b,a%b); }

唯一分解定理： 算术基本定理可表述为：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积

推论：最小公倍数LCM

gcd(a,b)∗lcm(a,b)=a∗b

Eratosthenes 筛法：

对于不超过n的每个负整数p，删除 2p,3p,4p,..., 当处理完所有数后，还没被删除的为素数。

void check_PRime(){ int vis[1005]; int n = 1000; memset(vis,0,sizeof(vis)); for(int i=2;i<=n;i++) for(int j=i*2;j<=n;j+=i) vis[j] = 1; for(int i=2;i<=n;i++) printf("%d ",vis[i]); }

相关推荐