27 数论 素数和约数

1  判断是否为素数

1.  
   /*
2.  
   学acwing的算法基础课学来的，喜欢的话多多支持呀。
3.  
   */
4.  
   //判断一个数是否是素数，用试除法，时间复杂的O(根号n)
5.  
   #include<bits/stdc .h>
6.  
   using namespace std;
7.  
   bool prime(int n)
8.  
   {
9.  
   if(n<2) return false;
10.  
    for(int i=2;i<=n/i;i )
11.  
    if(n%i==0) return false;
12.  
    return true;
13.  
    }
14.  
    int main()
15.  
    {
16.  
    int m;
17.  
    cin>>m;
18.  
    while(m--)
19.  
    {
20.  
    int n;
21.  
    cin>>n;
22.  
    if(prime(n)) puts("Yes");
23.  
    else puts("No");
24.  
    }
25.  
    return 0;
26.  
    }
27.  
     
28.  
    /*到达胜利之前无法回头*/

2  分解质因数

1.  
   /*
2.  
   学acwing的算法基础课学来的，喜欢的话多多支持呀。
3.  
   */
4.  
   //分解质因数,用试除法，时间复杂的O(根号n)
5.  
   #include<bits/stdc .h>
6.  
   using namespace std;
7.  
   void divide(int n)
8.  
   {
9.  
   for(int i=2;i<=n/i;i )
10.  
    if(n%i==0)
11.  
    {
12.  
    int s=0;//用s来记录
13.  
    while(n%i==0)//用来判断第i这个因子有多少个
14.  
    {
15.  
    n/=i;
16.  
    s ;
17.  
    }
18.  
    printf("%d %d\n",i,s);
19.  
     
20.  
    }
21.  
    if(n>1) printf("%d %d\n",n,1);
22.  
    }
23.  
    int main()
24.  
    {
25.  
    int m;
26.  
    scanf("%d",&m);
27.  
    while(m--)
28.  
    {
29.  
    int n;
30.  
    scanf("%d",&n);
31.  
    divide(n);
32.  
    }
33.  
    return 0;
34.  
    }
35.  
     
36.  
    /*到达胜利之前无法回头*/

3  筛质数 求1~n中素数个数

1.  
   /*
2.  
   学acwing的算法基础课学来的，喜欢的话多多支持呀。
3.  
   */
4.  
   //诶氏筛法 时间复杂的O(nloglogn)
5.  
   #include<bits/stdc .h>
6.  
   using namespace std;
7.  
   const int N=1e6 10;
8.  
   int primes[N],cnt;//prime用来存素数，cnt存个数
9.  
   bool st[N];//用来记录合数
10.  
    void get_primes(int n)
11.  
    {
12.  
    for(int i=2;i<=n;i )
13.  
    {
14.  
    if(!st[i])//假如是质数
15.  
    {
16.  
    primes[cnt ]=i;
17.  
    for(int j=i;j<=n;j =i) st[j]=true;//可以用质数就把所有的合数都筛掉，标记合数
18.  
    }
19.  
    }
20.  
    }
21.  
    int main()
22.  
    {
23.  
    int n;
24.  
    scanf("%d",&n);
25.  
    get_primes(n);
26.  
    cout<<cnt<<endl;
27.  
    return 0;
28.  
    }
29.  
    /*到达胜利之前无法回头*/

1.  
   /*
2.  
   学acwing的算法基础课学来的，喜欢的话多多支持呀。
3.  
   */
4.  
   //线性筛法 时间复杂度O(n)
5.  
   #include<bits/stdc .h>
6.  
   using namespace std;
7.  
   const int N=1e6 10;
8.  
   int primes[N],cnt;//prime用来存素数，cnt存个数
9.  
   bool st[N];//用来记录合数
10.  
    void get_primes(int n)
11.  
    {
12.  
    for(int i=2;i<=n;i )//外层从2~n迭代，因为这毕竟算的是1~n中质数的个数，而不是某个数是不是质数的判定
13.  
    {
14.  
    if(!st[i]) primes[cnt ]=i;//判断是不是标记过，没的话则为素数，放进primes里
15.  
    for(int j=0;primes[j]<=n/i;j )//判断一个数有没有最小因子
16.  
    {
17.  
    st[primes[j]*i]=true;//用最小质因子去筛合数，标记素数的倍数为合数
18.  
    if(i%primes[j]==0) break;//假如没有则跳出来
19.  
    }
20.  
    }
21.  
    }
22.  
    int main()
23.  
    {
24.  
    int n;
25.  
    scanf("%d",&n);
26.  
    get_primes(n);
27.  
    cout<<cnt<<endl;
28.  
    return 0;
29.  
    }
30.  
    /*到达胜利之前无法回头*/

4 试除法求约数

1.  
   /*
2.  
   学acwing的算法基础课学来的，喜欢的话多多支持呀。
3.  
   */
4.  
   //试除法求约数 时间复杂度O(根号n)
5.  
   #include<bits/stdc .h>
6.  
   using namespace std;
7.  
   vector<int> get_divisors(int n)//试除法求约数
8.  
   {
9.  
   vector<int> res;//一个int数组存约数
10.  
    for(int i=1;i<=n/i;i )
11.  
    if(n%i==0)//假如是约数
12.  
    {
13.  
    res.push_back(i);//放进数组中
14.  
    if(i!=n/i) res.push_back(n/i);//假如另一个约数不相同，则也放进数组中
15.  
    }
16.  
    sort(res.begin(),res.end());//从小到大排序一遍
17.  
    return res;
18.  
    }
19.  
    int main()
20.  
    {
21.  
    int n;
22.  
    scanf("%d",&n);
23.  
    while(n--)
24.  
    {
25.  
    int x;
26.  
    scanf("%d",&x);
27.  
    auto res=get_divisors(x);
28.  
    for(auto t:res) printf("%d ",t);//输出数组的每一个数
29.  
    puts("");
30.  
    }
31.  
    return 0;
32.  
    }
33.  
    /*到达胜利之前无法回头*/

 5 求约数的个数

1.  
   /*
2.  
   学acwing的算法基础课学来的，喜欢的话多多支持呀。
3.  
   */
4.  
   //求约数个数，结合哈希表来存数，套用一个公式前面图片有
5.  
   #include<bits/stdc .h>
6.  
   using namespace std;
7.  
   typedef long long ll;
8.  
   const int mod=1e9 7;
9.  
   int main()
10.  
    {
11.  
    int n;
12.  
    scanf("%d",&n);
13.  
    unordered_map<int,int> hash;//定义一个hash表，来记录这个数的几次幂
14.  
    while(n--)
15.  
    {
16.  
    int x;
17.  
    scanf("%d",&x);
18.  
    for(int i=2;i<=x/i;i )//用来算一个数能能分解一个数的几次幂
19.  
    while(x%i==0)
20.  
    {
21.  
    x/=i;
22.  
    hash[i] ;
23.  
    }
24.  
    if(x>1) hash[x] ;
25.  
     
26.  
    }
27.  
    ll res=1;//用来记录答案
28.  
    for(auto t:hash) res=res*(t.second 1)%mod;//结果可能比较大，对1e9 10取模
29.  
    printf("%lld\n",res);
30.  
    return 0;
31.  
    }
32.  
    /*到达胜利之前无法回头*/

 6 求约数之和

1.  
   /*
2.  
   学acwing的算法基础课学来的，喜欢的话多多支持呀。
3.  
   */
4.  
   //求约数之和，结合哈希表来存数，套用一个公式前面图片有
5.  
   #include<bits/stdc .h>
6.  
   using namespace std;
7.  
   typedef long long ll;
8.  
   const int mod=1e9 7;
9.  
   int main()
10.  
    {
11.  
    int n;
12.  
    scanf("%d",&n);
13.  
    unordered_map<int,int> hash;//定义一个hash表，来记录这个数的几次幂
14.  
    while(n--)
15.  
    {
16.  
    int x;
17.  
    scanf("%d",&x);
18.  
    for(int i=2;i<=x/i;i )//用来算一个数能能分解一个数的几次幂
19.  
    while(x%i==0)
20.  
    {
21.  
    x/=i;
22.  
    hash[i] ;
23.  
    }
24.  
    if(x>1) hash[x] ;
25.  
     
26.  
    }
27.  
    ll res=1;//用来记录答案
28.  
    for(auto t:hash)
29.  
    {
30.  
    int p=t.first,a=t.second;//p是当前的数，a是当前p的指数
31.  
    ll m=1;
32.  
    while(a--) m=(m*p 1)%mod;//算公式中的一部分
33.  
    res=res*m%mod;//安照公式把每一个部分乘起来
34.  
    }
35.  
    printf("%lld\n",res);//输出答案
36.  
    return 0;
37.  
    }
38.  
    /*到达胜利之前无法回头*/

7 求最大公约数

1.  
   /*
2.  
   学acwing的算法基础课学来的，喜欢的话多多支持呀。
3.  
   */
4.  
   //求最大公约数，用欧几里得算法（辗转相除法）
5.  
   #include<bits/stdc .h>
6.  
   using namespace std;
7.  
   int gcd(int a,int b)
8.  
   {
9.  
   return b?gcd(b,a%b):a;//用递归实现辗转相除法
10.  
    }
11.  
    int main()
12.  
    {
13.  
    int n;
14.  
    scanf("%d",&n);
15.  
    while(n--)
16.  
    {
17.  
    int a,b;
18.  
    scanf("%d%d",&a,&b);
19.  
    printf("%d\n",gcd(a,b));
20.  
    }
21.  
    return 0;
22.  
    }
23.  
    /*到达胜利之前无法回头*/

这篇好文章是转载于：学新通技术网