质数

定义

　　质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。

定理

　　算数分布定理：

　　　　　　1.任何一个大于1的正整数都能唯一分解为有限个质数的乘积

　　　　　　2.其中参与乘积的质数的幂为单调递减数列

　　质数分布定理：

　　　　　　1.对于正实数X，定义f(x)为不大于x的质数的个数，那么 f(x)≈x/㏑x

　　　　　　2.第n个质数p(n)的渐进估计：p(n)=n㏑n

质数的判定

　　试除法：

　　　　　　定理：若一个正整数是合数，则存在一个能整除N的数K,2≤K≤sqrt(n)

　　　　　　证明：反证法

质数的筛选

　　Eratosthens筛选法

　　　　　　基本思想：质数的倍数一定不是质数

　　　　　　时间复杂度: O(n㏒㏒n)

　　欧拉线性筛　　

1. 1. 由于每个大于等于2的合数必定存在一个最小的质因数，所以只要筛去每个质数的倍数就相当于筛去了所有合数。
   2. 但欧拉筛相比埃氏筛最大的优化就在于欧拉筛保证每个合数只被筛了一次，且是被其最小的质因数筛去的，所以欧拉筛的时间复杂度可以达到O(N)。

　　　　　　代码

#include<stdio.h>
#include<stdlib.h>
#define FORa(i,s,e) for(int i=s;i<=e;i++)
#define FORs(i,s,e) for(int i=s;i>=e;i--)
#define gc pa==pb&&(pb=(pa=buf)+fread(buf,1,100000,stdin),pa==pb)?EOF:*pa++
#define File(name) freopen(name".in","r",stdin);freopen(name".out","w",stdout);

using namespace std;
static char buf[100000],*pa=buf,*pb=buf;
inline int read();

const int N=1000;
int n,cnt,v[N+1],prime[N+1]; 
int main()
{
    scanf("%d",&n);
    /*优化空间的欧拉质数筛 FORa(i,2,n)
    {
        if(!bz[i]) prime[++cnt]=i;
        FORa(j,1,cnt)
        {
            if(i*prime[j]>n) break;
            bz[i*prime[j]]=true;
            if(i%prime[j]==0)
                break;
        }
    }*/ 
    FORa(i,2,n)
    {
        if(!v[i]) v[i]=i,prime[++cnt]=i;
        FORa(j,1,cnt)
        {
            if(prime[j]>v[i]||prime[j]*i>n) break; 
            /*因为整个程序会经过整个队列，所以可以保证都会被筛 
            prime[j]>v[i]是为了prime[j]*i不被再次被筛
            如果 prime[j]>v[i]就说明之后的v[prime[j]*i]在后续就会被筛 */ 
            v[prime[j]*i]=prime[j];
        }
    }
    FORa(i,1,cnt) printf("%d ",prime[i]);
    return 0;
}
inline int read()
{
    register int x(0);register int f(1);register c(gc);
    while(c<'0'||c>'9') f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=gc;
    return  x*f;
}

质因数分解

　　　　算术基本定理：

　　　　　　1.任何一个大于1的正整数都能唯一分解为有限个质数的乘积

　　　　　　2.其中参与乘积的质数的幂为单调递减数列