数论 - 质数(素数)基础【素数的判断 + 试除法分解质因数 + 求1-n之间的素数的三种筛法】

女爷i 2021-07-24 18:57 533阅读 0赞

## **数论-质数基础** ##

### **1.素数** ###

素数又称为质数，是指除了1和本身之外，不能被其他数整除的一类数。即对给定的正整数n,如果对任意的正整数a(1<a<n)，都有n%a!=0成立，那么称n是素数;否则，如果存在a(1<a<n),使得n%a==0，那么称n为合数。应特别注意的是，1既不是素数，也不是合数。

### **2.素数的判断** ###

##### 试除法 #####

bool is_prime(int x)
    { 
    	if (x < 2) return false;
    	for (int i = 2; i <=x / i; i++)
    	{ 
    		if (x%i == 0)
    		{ 
    			return false;
    		}
    	}
    	return true;
    }

for()循环中有三种写法(1). i \* i<=n 这样写当n接近int型变量的范围上限时会导致i \* i溢出。  
(2) i<=sqrt(n) 每次循环都要计算sqrt(n) ,浪费时间。  
(3) i<=n/i 这种写法的效率高而且安全。

### **3.试除法分解质因数** ###

//试除法分解质因数
    void divide(int x)
    { 
    	for (int i = 2; i <= x / i; i++)
    	{ 
    		if (x%i == 0)
    		{ 
    			int s = 0; //统计每个质因数的个数
    			while (x%i == 0)
    			{ 
    				x /= i;
    				s++;
    			}
    			cout << i << " " << s << endl;
    		}
    	}
    	if (x > 1) cout << x << " " << 1 << endl;  //大于sqrt(n)的质因数只有一个，n本身
    	cout << endl;
    }

### **4.筛法求1-n之间的素数** ###

##### (1).最普通的筛法 O(nlogn) #####

int primes[N], cnt;     // primes[]存储所有素数
    bool st[N];         // st[x]存储x是否被筛掉 
    void get_primes(){ 
        for(int i=2;i<=n;i++){ 
    
            if(!st[i]) primes[cnt++]=i;//把素数存起来
            for(int j=i;j<=n;j+=i){ //不管是合数还是质数，都用来筛掉后面它的倍数
                st[j]=true;
            }
        }
    }

##### (2).诶氏筛法 O(nloglogn) #####

int primes[N], cnt;     // primes[]存储所有素数
    bool st[N];         // st[x]存储x是否被筛掉 
    void get_primes(){ 
        for(int i=2;i<=n;i++){ 
            if(!st[i]){ 
                primes[cnt++]=i;
                for(int j=i;j<=n;j+=i) st[j]=true;//可以用质数就把所有的合数都筛掉；
            }
        }
    }

##### (3).线性筛法 O(n) #####

用一个合数的最小质因子去筛这个合数

//线性筛法-O(n), n = 1e7的时候基本就比埃式筛法快一倍了
    //算法核心：x仅会被其最小质因子筛去
    int primes[N], cnt;     // primes[]存储所有素数
    bool st[N];         // st[x]存储x是否被筛掉 
    void get_primes(int x) { 
        for(int i = 2; i <= x; i++) { 
            if(!st[i]) prime[cnt++] = i;
            for(int j = 0; prime[j] <= x / i; j++) { 
                //对于任意一个合数x，假设pj为x最小质因子，当i<x/pj时，一定会被筛掉
                st[prime[j]*i] = true;
                if(i % prime[j] == 0) break;
                /* 1.i%pj == 0, pj定为i最小质因子，pj也定为pj*i最小质因子 2.i%pj != 0, pj定小于i的所有质因子，所以pj也为pj*i最小质因子 */
            }
        }
    }

### **5.题目练习** ###

##### (1) **AcWing 866. 试除法判定质数** #####

给定n个正整数ai，判定每个数是否是质数。  
**输入格式**  
第一行包含整数n。  
接下来n行，每行包含一个正整数ai。  
**输出格式**  
共n行，其中第 i 行输出第 i 个正整数ai是否为质数，是则输出“Yes”，否则输出“No”。  
**数据范围**  
1≤n≤100,  
1≤ai≤2∗109  
**输入样例：**  
2  
2  
6  
**输出样例：**  
Yes  
No  
**代码**

#include<iostream>
    #include<cstdio>
    using namespace std;
    bool is_prime(int x)
    { 
    	if (x < 2) return false;
    	for (int i = 2; i <= x / i; i++)
    	{ 
    		if (x%i == 0) return false;
    	}
    	return true;
    }
    int main()
    { 
    	int n;
    	cin >> n;
    	while (n--)
    	{ 
    		int x;
    		cin >> x;
    		if (is_prime(x))
    		{ 
    			cout << "Yes" << endl;
    		}
    		else
    		{ 
    			cout << "No" << endl;
    		}
    	}
    	return 0;
    }

##### (2)AcWing-867. 分解质因数 #####

给定n个正整数ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。  
**输入格式**  
第一行包含整数n。  
接下来n行，每行包含一个正整数ai。  
**输出格式**  
对于每个正整数ai,按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。  
每个正整数的质因数全部输出完毕后，输出一个空行。  
**数据范围**  
1≤n≤100,  
1≤ai≤2∗109  
**输入样例：**  
2  
6  
8  
**输出样例：**  
2 1  
3 1  
2 3  
**代码**

//试除法分解质因数
    #include<iostream>
    #include<cstdio>
    using namespace std;
    void divide(int x)
    { 
    	for (int i = 2; i <= x / i; i++)
    	{ 
    		if (x%i == 0)
    		{ 
    			int s = 0; //统计每个质因数的个数
    			while (x%i == 0)
    			{ 
    				x /= i;
    				s++;
    			}
    			cout << i << " " << s << endl;
    		}
    	}
    	if (x > 1) cout << x << " " << 1 << endl;  //大于sqrt(n)的质因数只有一个，n本身
    	cout << endl;
    }
    int main()
    { 
    	int n;
    	cin >> n;
    	while (n--)
    	{ 
    		int x;
    		cin >> x;
    		divide(x);
    	}
    	return 0;
    }

##### (3)AcWing-868. 筛质数 #####

给定一个正整数n，请你求出1~n中质数的个数。  
**输入格式**  
共一行，包含整数n。  
**输出格式**  
共一行，包含一个整数，表示1~n中质数的个数。  
**数据范围**  
1≤n≤106  
**输入样例：**  
8  
**输出样例：**  
4  
**代码**

#include<iostream>
    #include<cstdio>
    using namespace std;
    const int maxn = 1e6 + 10;
    int primes[maxn],cnt; //存储所有素数
    bool st[maxn];  //st[x]存储x是否被筛掉
    //朴素筛法
    //void get_primes(int n)
    //{ 
    // for (int i = 2; i <= n; i++)
    // { 
    // if (!st[i]) primes[cnt++] = i;
    // for (int j = i + i; j <= n; j += i)
    // { 
    // st[j] = 1;
    // }
    // }
    //}
    //线性筛法
    void get_primes(int n)
    { 
    	for (int i = 2; i <= n; i++)
    	{ 
    		if (!st[i])  primes[cnt++] = i;
    		for (int j = 0; primes[j] <= n / i; j++)
    		{ 
    			st[primes[j] * i] = 1;
    			if (i%primes[j] == 0)  break;
    		}
    	}
    }
    int main()
    { 
    	int n;
    	cin >> n;
    	get_primes(n);
    	cout << cnt << endl;
    	return 0;
    }