C++ 6.8笔记:①判断质数②二分基础算法

质数

试除法判定质数

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

埃筛1

int p[N],k,n;
bool f[N];
void primes(int n){ //埃筛，思想：质数的倍数是合数
    for(int i=2;i<=n;i++){
        if(f[i]==0){     //是质数
            p[++k]=i;   //质数存储
            for(int j=i*i;j<=n;j+=i) f[j]=1;
        }
    }
}
/*
内层for优化，即质数的倍数是合数，而合数不用重复枚举；
另外，从i*i开始也是优化步骤
*/

埃筛2

int p[N],k,n;
bool f[N];
void primes(int n){  //埃筛，sqrt(n)次遍历
    for(int i=2;i<=n/i;i++){
        if(f[i]==0){ //是质数
            for(int j=i*i;j<=n;j+=i){
                if(f[j]==0) f[j]=1; 
            } 
        }
    }
    for(int i=2;i<=n;i++){
        if(f[i]==0) p[++k]=i;
    }
}

线筛（欧拉筛）

int p[N],k,n;
bool f[N];
void primes(int n){  //线筛，思想：合数被它最小的质数筛掉
    for(int i=2;i<=n;i++){
        if(f[i]==0) p[++k]=i;  //如果是质数，存储
        for(int j=1;p[j]<=n/i;j++){ //遍历现有质数表
            f[i*p[j]]=1;      //i倍的质数组成的合数
            if(i%p[j]==0) break; //合数被最小的质数筛掉，即合数i%p[j]应该被最小的p[j]筛掉
        }
    }
}

算术基本定理（唯一分解定理）

int n,p[N],cnt[N],k;
int decompos(int n){
    int m=0;
    for(int i=2;i<=n/i;i++){
        if(n%i==0){
            p[++m]=i;   //存储质数
            while(n%i==0){
                n/=i;
                cnt[m]++;   //存储对应的质数数量
            }
        }
    }
    if(n>1){    //剩余的质数以及数量
        p[++m]=n;
        cnt[m]=1;
    }
    return m;
}

二分

定义

过程

实现步骤

模板代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n,tan;
	cin >> n;
	int a[n];
	for(int i = 0;i < n;i ++)
		cin >> a[i];
	int left=0,right=n-1,mid;
	cin >> tan;
	while(left<=right)
	{
		mid = (left+right)/2;
		if(a[mid] > tan)
		{
			right = mid - 1;
		}
		else
		{
			left = mid + 1;
		} 
	}
	printf("%d",left);
	return 0;
} 

适用范围

需要有边界，有限