素数相关问题练习 C++

辗转相除

#include <iostream>
using namespace std;

int gcb(int a,int b)
{
    if(b==0) return a;
    return gcb(b,a%b);
}

int main()
{
    int a,b;
    cin>>a>>b;
    cout<<gcb(a,b);
}

素数判定

#include <stdio.h>
#include <math.h>
#include <vector>
using namespace std;

bool is_prime(int x)
{
    for(int i=2;i*i<=n;i++)
    {
        if(x%i==0)
        {
            return false;
        }
    }
    return x!=1;
}

vector<int> divisor(int x)
{
    vector<int> res;
    float sq = sqrt(x);
    for(int i=2;i<=int(sq);i++)
    {
        if(x%i==0)
        {
            res.push_back(i);
            if(i!=x/i) res.push_back(x/i);
        }
    }
    return res;
}

map<int,int> prime_factor(int x)
{
    map<int,int> res;
    for(int i=2;i*i<x;i++)
    {
        while(n%i==0)
        {
            ++res[i];
            x /= i;
        }

    }
    if(x!=1) res[n]=1;
    return res;
}

int main()
{
    printf("%d\n",is_prime(0));
    printf("%d\n",is_prime(1));
    printf("%d\n",is_prime(8));
    printf("%d\n",is_prime(7));
}

埃氏筛法

#include<stdio.h>
#include<iostream>
#include <algorithm>
using namespace std;
const int MAX=1000000;
int arr[MAX];

int solve(int n)
{
    cout<<"solve"<<endl;
    int res=0;

    fill(arr,arr+n,0);
    cout<<"fill done"<<endl;
    for(int i=2;i<n;i++)
    {
        if(!arr[i])
        {
            cout<<"arr["<<i<<"]"<<endl;
            int flag = 0;
            for(int j=2;j*j<=i;j++)
            {
                if(i%j==0)
                {
                    flag = 1;
                    break;
                }
            }
            if(flag==0)
            {
                res++;
                for(int p=1;p*i<=n;p++)
                {
                    arr[p*i]=1;
                }
            }
        }
    }
    return res;
}

int main()
{
    printf("%d\n",solve(15));
    return 0;
}