算法基础之筛质数

2023-12-20 23:10:13

筛质数

  • 核心思想:筛法求质数

埃氏筛法:

  • 每次用 2 3 4…. p-1 筛 2 - p之间的数
  • 出现2 3 4 …的倍数时 去掉(4实际已经被去掉 不会用4去筛)
  • 当2~p-1的数都没有筛掉p 说明p是质数
    • 优化: 只用2~p-1中质数筛

线性筛法:

  • 核心: n只会被其最小质因子筛掉

    • 在这里插入图片描述

    • 每一个合数都只会被筛一次,因为每个合数的最小质因数都是唯一的

    •   #include<iostream>
        #include <algorithm>
        
        using namespace std;
        const int N = 1000010;
        
        int prime[N],cnt;
        bool st[N];
        
        void get_prime(int n)
        {
            for(int i = 2;i<=n;i++)
            {
                if(!st[i]) prime[cnt++] = i;  //如果没被筛掉 记录成质数
                for(int j = 0;prime[j] <= n/i ; j ++)  //从小到大遍历所有质数
                {
                    st[prime[j] * i] = true;  //将prime[j]的倍数筛掉
                    if(i % prime[j] == 0) break;  //如果i % prime[j] == 0 说明i是prime[j]的倍数
                    							  //那么当prime[j+1]的时候 prime[j+1]*i的最小质因数是prime[j] 而不是prime[j+1]
                }
            }
        }
        
        int main()
        {
            int n;
            cin>>n;
            
            get_prime(n);
            
            cout<<cnt;
        }
      

文章来源:https://blog.csdn.net/Pisasama/article/details/135118099
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。