【数学知识】 |质数，素数| 筛选质数，分解质因数|简单的数学结论

大家好，欢迎来到IT知识分享网。

一，质数

1，质数

质数又被叫做素数,首先我们看一下质数的定义，质数是指只能被1和自身整除的正整数。

换句话说，一个数如果除了1和本身之外不再有其他因数，那么这个数就是质数。例如，2、3、5、7、11、13等都是质数。而4、6、8、9、10等数则不是质数。

判断质数常见问题

当这个小于等于1的数都不是质数
小于0的不是质数
2是质数
这些负半轴的值是最容易出现边界判断错误的。

2，质因数

质因数全部都是质数组成的，用分解的方法，把他分解成 n = 质数1 * 次数1 * 质数2 * 次数2 * …
小学的分解质因数，相当于…，看个图

二，是否为质数

is or not is prime 最关键的就是定义上所表示的，只有1和他本身能除以他Mod 0 ，上朴素

#include <iostream> using namespace std ; int n ; bool is_prime () { 
    if( n <= 1) return false ; for ( int i = 2 ; i < n ; i ++ ) if(n % i == 0) return false ; return true ; } int main () { 
    cin >> n ; if(is_prime()) cout << "YES , is prime" ; else cout << "NO , is not prime" ; cout << endl ; return 0 ; } 

简化，首先这个算法肯定是一个 O（N） 的时间复杂度，我们知道因子总是成对出现的，最大的因子为 i * i = n ,我们只用遍历到这个值就可以了，

//仅仅修改上文第六行 for(int i = 2 ; i <= n / i ; i ++ ) 

首先来说这个 i的处理最好是 i <= n / i ，其他方法可能报错，不再细讲

三，分解质因数

两个点， 一个是整体的遍历从二，到也是最大也只能 n / i ，并且在递归的操作中减去出来的值，遍历O（N）是最大的时间复杂度

#include <iostream> using namespace std ; int n ; void prime_son() { 
    for(int i = 2 ; i <= n / i ; i ++ ) { 
    if(n % i == 0) { 
    int ans = 0; while ( n % i == 0) { 
    n /= i ; ans ++ ; } cout << i << " " << ans << endl ; } } if(n != 1) cout << n << " " << 1 << endl ; return ; } int main () { 
    cin >> n ; prime_son() ; return 0 ; } 

四，搜索前n个数中有几个质数

我们知道在前n个数中来搜索质数，本质上只有一种方法，就是把已知的质数对前面进行赋值操作，最简单的操作是每次我们都赋值一次

#include <iostream> using namespace std ; const int N = 1e6 + 10; bool st[N] ; int get_prime(int n ) { 
    int ans = 0 ; for( int i = 2 ; i <= n ; i ++ ) { 
    if(!st[i]) ans ++ ; for(int j = i ; j <= n ; j += i ) st[j] = true ; } return ans ; } int main () { 
    int n ; cin >> n ; cout << get_prime(n) << endl ; return 0 ; } 

但是我们也可以每次用他的质数的因子来完成这个操作

#include <iostream> using namespace std ; int n ; const int N = 1e6 + 10 ; int prime[N] ; int cnt = 0 ; bool st[N] ; int get_prime() { 
    for(int i = 2 ; i <= n ; i ++ ) { 
    if(!st[i]) prime[++ cnt] = i ; for(int j = 1; prime[j] <= n / i ; j ++ ) { 
    st[prime[j] * i ] = true ; if(i % prime[j] == 0 ) break ; } } return cnt ; } int main () { 
    cin >> n ; cout << get_prime() << endl ; return 0 ; } 

这个时间复杂度为O(N) 所以被称为线性筛法，我们来讲解一下原理，首先每次我们先取质数操作 ，再对下面的质数集合对这个点进行赋值操作，然后到点弹出。