首页 > 代码库 > 【模版】素数筛, 最大公约数（辗转相除法），最小公倍数

【模版】素数筛, 最大公约数（辗转相除法），最小公倍数

2024-07-18 11:15:13   225人阅读

素数筛：

//数除了{2,3,5}为素数，其他的数可以写成6N，6N+1,6N+2,6N+3,6N+4,6N+5  N>=1 可以表示全部的数
//6N，6N+2,6N+4都为偶数，不是素数，6N+3 == 3(2N+1) 不是素数，那么就只筛6N+1和6N+5就可以了
int prime[1000000]={2,3,5};
void is_prime()
{
    int i,j;
    int flag=0;//标记
    int gcd=2;
    int k=3;//素数的下标，因为已有三个，所以下一个出现的宿舍从k=3开始
    for(i=7;i<=1000000;i+=gcd)
    {
        flag=0;
        gcd=6-gcd;//6N+1和6N+5的变换
        for(j=0;prime[j]*prime[j]<=i;j++)//因为一个开根号比乘法是要慢的，所以用乘法速度更快。
        {
            if(i%prime[j]==0)
            {
                flag=1;
                break;
            }
        }
        if(flag==0)//若这个数没有被其他素数整除 说明为素数
        {
            prime[k++]=i;
        }
        
    }
}

点我看题->传送


最大公约数：

int gcd(int a,int b)
{
    while(b!=0)
    {
        int r=b;
        b=a%b;
        a=r;
    }
    return a;
}

最小公倍数

因为最小公倍数lcm（a，b）*gcd（a，b）=a*b；有了公式也不能大意，如果把lcm（a，b）写成a*b/gcd（a，b）可能会超内存，因为a*b可能会溢出。所以正确的写法应该是先除后乘，即a/gcd（a，b）*b；

lcm(a,b)=a/gcd(a,b)*b


联系
我们