輾轉(zhuǎn)相除
#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);
}
素?cái)?shù)判定
#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;
}
