如果n是合数, 则n必有一个小于或等于n1/2的素因子
筛法求素数：埃式筛法
const int maxn=100000; bool isprime[maxn]; void searchPrime(int n) {memset(isprime,true,sizeof(isprime)); isprime[1]=false; for (i=2; i*i<=n; i++) if (isprime(i)) {j=i*i; while (j<=maxn) {isprime[j]=false; j+=i;} } }
欧拉筛法：原理：线性筛法的核心原理就是一句话： 每个合数必有一个最大因子（不包括它本身） ，用这个因子把合数筛掉，还有另一种说法（每个合数必有一个最小素因子，用这个因子筛掉合数）
void seive( int Max ) { memset( isPrime , true , sizeof( isPrime )); isPrime[0 ] = false ; isPrime[1] = false ; for ( int i = 2 ; i <= Max ; i++ )//遍历筛去所有最大因数是i的合数 {if ( isPrime[i] ) prime[ ++ total ] = i ;//把素数记录下来 //遍历已知素数表中比i的最小素因数小的素数，并筛去合数 for ( int j = 1 ; j <= total && i * prime[j] <= Max ; j++) { isPrime[ i * prime[j] ] = false ; if (!( i % prime[j])) break;//找到i的最小素因数 } } }
唯一分解定理：每个正整数都可以惟一地表示成素数的乘积，其中素数因子从小到大依次出现（这里的“乘积”可以有0个、1个或多个素因子）。即对任一整数a＞1，有a= p1a1p2a2…pnan ，其中p1<p2<…<pn均为素数，而a1,a2…,an是正整数。
同余式概念：当且仅当m|(a-b)时，我们称a和b对模m同余，记作a≡b(mod m)（这里总设m>0) 本质上，m|(a-b)和a≡b(mod m)只不过是同一性质的不同表示法而已。 同余式的记号是高斯(Gauss)在1800年左右首创的，它看起来有点象等式的记号。事实上，我们以后会看到，同余式和等式有着许多共同的性质。
基本性质：①已知(a，c)=1，若a | bc，则a | b；若a | b，c | b，则ac | b ②p为素数，若p | ab，则p | a或p | b ③[a，b]·(a，b)=ab ④(a，b)=(a，b－ac)=(a－bc，b) ⑤(n，n-1)=1 或 (n，n-p)≤p ⑥m(a，b)=(ma，mb) ⑦若(a，b)=d，则(a/d,b/d)=1 ⑧若a | m，b | m，则[a，b] | m
⑨m[a，b]=[ma，mb]
两个定理：威尔逊定理：若p为素数，则(p-1)!≡-1 (mod p)。 威尔逊定理的逆定理也成立，即：若对某一正整数p，有(p-1)!≡-1 (mod p)，则p一定为素数。
费马小定理：p是素数且(a,p)=1，则ap-1≡1 (mod p)
欧拉函数: 1~n中和n互素的元素个数(n) Euler定理: 若gcd(a, n)=1则a(n) 1 (mod n) 意义：当b很大时，ab ab mod n)(mod n)，让指数一直比较小 可见，费马小定理是欧拉定理的特例。
一个正确的结论：对于任意的a,n,b，当b>(n)时，则有ab a(n) + b mod (n) (mod n)
代码实现：
#include<bits/stdc++.h>using namespace std;int main(){ int n,k=2; cin>>n; int ans=n; while(k*k<=n) { if(n%k==0) { ans=ans*(k-1)/k;while(n%k==0) { n/=k; } } k++; } if(n>1) ans=ans*(n-1)/n; cout<<ans; return 0;}明天的数论明天再补滚去写作业了(产量真高)
