数论

有关因子数的解法

Posted by Liao on 2019-12-03

一. 求因子的个数

题意大概是，输入一个数，输出这个数因子的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int cnt = 2;  //一个数本身有两个因子，1和它本身。
    for(int i=2;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
           if(i == sqrt(n) && n%i == i)  //如果两因子相同，因子数加1；否则加2。
                cnt += 1;
           else
                cnt += 2;
        }
    }
    if(n == 1)
        cout << "1" << endl;
    else
        cout << cnt << endl;

}


​

二.

1

![](求因子个数/2019-12-03 11-45-30屏幕截图.png)

  • 首先预处理数组，预处理出1~1000000的因子数，然后再进行查询，这样能够减少查询时间。
  • 1的因子只有自己，从2开始，若遍历到两个因子数相同，则加1；若不同则加2。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MOD = 1073741824;
const int MAXN = 1e6 + 10;
int arr[MAXN];

void init()
{
    arr[1] = 1;
    for(int i=2;i<MAXN;i++)
        arr[i] = 2;

    for(int i=2;i*i<MAXN;i++)
    {
        for(int j=i;j*i<MAXN;j++)
        {
            if(i == j)
                arr[i*j] += 1;
            else
                arr[i*j] += 2;
        }
    }
}
int main()
{
    int a,b,c;
    int ans = 0;
    init();  //初始化数组，处理因子
    scanf("%d %d %d",&a,&b,&c);
    for(int i=1;i<=a;i++)
    {
        for(int j=1;j<=b;j++)
        {
            for(int k=1; k<=c;k++)
            {
                ans = ans + arr[i*j*k];
                if(ans > MOD)
                    ans = ans % MOD;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}


三. L1-006 连续因子

3

  • 首先求出这个数是否是素数，如果是最长连续因子只有它自己，为1，并且输出它自身即可。

  • 如果不是素数，通过循环每次记录最长因子的个数，以及打头的数，最后把那个区间里的数打印出来即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <cmath>
using namespace std;

int isPrime(int n)  //判断素数
{
    for(int i=2;i<=sqrt(n)+1;i++)
    {
        if(n%i==0)
            return 0;
    }
    return 1;
}

int main()
{
    int n,sum,maxn=0,i,j,flag=0;
    cin >> n;
    if(isPrime(n))
    {
         cout << "1" << endl; //如果是素数，则最长连续因子个数是1
         cout << n <<endl;
    }
    else
    {
        for(i=2;i<=sqrt(n)+1;i++)
        {
            if(n%i ==0)
            {
                sum = i;          //重新初始化i
                for(j=i+1;j<=sqrt(n)+1;j++)  //i和j连续判断
                {
                    sum = sum*j;
                    if(n%sum != 0)
                        break;
                }
                if((j-i)>maxn)
                {
                    maxn = j-i;  //最长连续因子个数
                    flag = i;    //打头的那个数
                }
            }
        }
        cout << maxn <<endl;
        
        //flag是打头那个数，maxn是最长连续因子个数，把这个区间里面的数打印出来
        for(i=flag;i<(flag+maxn);i++)  
        {
            if(flag != i)
                cout << "*";
            cout << i;
        }
    }

    return 0;
}

LeetCode 丑数

只包含质因数的正整数就是丑数

通过while循环不断判断2,3,5是否num的质数，如果是则继续判断，直到num为1。

最后通过return判断num满不满足为1。

1
2
3
4
5
6
7
8
9
10
11
bool isUgly(int num) {
       if(num == 0)
           return false;
       while(num % 2 == 0)
           num /= 2;
       while(num % 3 == 0)
           num /= 3;
       while(num % 5 == 0 )
           num /= 5;
       return num == 1;
   }
FEATURED TAGS
数论
FRIENDS