大二进阶Java蓝桥杯亲密数

Question

//因子的和
public static int sum(int n) { 
    int sum=0;  
    for(int i=1;i<=n/2;i++){  
        if(n%i==0){  
            sum+=i;  
        }  
    }  
    return sum;  
}

这里的i<=n/2没搞懂是什么意思啊，感谢回答

Answer 1

因为大于 n/2 的数，除了 n，不可能是 n 的因子了。
比如 n=100， 那么 51 - 99 中不可能有 n 的因子。

因子和更好的求解方法可以看这个文章，在我专栏里，给你 免费搞出来 了

零、写在前面

  这是

《算法零基础100讲》 《算法零基础100讲》(第17讲) 线性枚举(一) - 最值算法,《算法零基础100讲》(第16讲) 变量交换算法,《算法零基础100讲》(第15讲) 二分快速幂,数据结构,算法,哈希标记 https://blog.csdn.net/whereisherofrom/category_11426012.html

专栏打卡学习的第十二天了。
  在刷题的过程中，总结自己遇到的坑点，写出 「 解题报告 」 供他人学习，也是一种自我学习的方式。这就是经典的帮助他人的同时，成就自己。目前，

「 万人千题 」 CSDN万人千题社区,万人千题论坛,为中国软件开发者打造学习和成长的家园 https://bbs.csdn.net/forums/hero

社区 每天都会有五六篇高质量的 「 解题报告 」 被我 「 加精 」。如果觉得自己有能力的，也可以来发布你的 「 解题报告 」。千万级流量，你我共同拥有。

一、概念定义

  如何求一个数 $n$ 的因子和呢？
  考虑数 $n$，令 $n$ 的因子和为 $s(n)$，对 $n$ 进行素数分解后的，假设最小素数为 $p$，素因子 $p$ 的个数为 $e$ ，那么 $$n = p^en'$$   容易得知，当 $n$ 的因子中 $p$ 的个数为 $0$ 时，因子之和为 $s(n')$。更加一般地，当 $n$ 的因子中 $p$ 的个数为 $k$ 的时候，因子之和为 $p^k * s(n')$，所以 $n$ 的所有因子之和就可以表示成：
$$\begin {aligned} s(n) &= (p^0 + p^1 + p^2 + ... p^e) * s(n') \ &= \frac {p^{e+1} - 1} {p-1} * s(n') \end {aligned}$$  $s(n')$ 可以通过相同方法递归计算。最后可以表示成一系列等比数列和的乘积。如下：
$$s(n) =\prod_{i=1}^k \frac {p_i^{e_i+1} - 1} {p_i-1} $$

二、题目描述

  给定一个 $n(n \le 10^4)$ 个整数的数组 $nums$，元素的范围小于等于 $10^5$ 的正整数，请你返回该数组中恰有四个因数的这些整数的各因数之和。

三、算法详解

  根据因子数的定义，有四个因子数的数，有两种情况：
    1）两个素数的乘积，即 $x=pq$；
    2）某个素数的三次幂，即 $x=p^3$；
  所以可以先对 10^5 内的所有的数进行素数筛选。然后遍历数组，对于每个数 $x$ ，进行 $[2, \sqrt x]$ 范围内的素数进行试除：
  如果能够分解成两个素数的乘积，则继续根据 因子和 的公式，计算因子和。具体的，如果 $x = pq$，则因子和为 $$\frac {p^2-1}{p-1} \frac {q^2-1}{q-1} = (p+1)(q+1)$$  如果能够分解一个素数的三次幂，则计算公式为：$$\frac {p^4-1}{p-1} = p^3+p^2+p+1$$

四、源码剖析

#define maxn 100001
#define ll long long

bool f[maxn];
int primes[maxn];

void ethPrime(){
    int i;
    ll j;                                       
    f[0] = f[1] = 1;
    primes[0] = 0;
    for(i = 2; i < maxn; ++i) {
        if(!f[i]) {
            primes[++primes[0]] = i;
            for(j = (ll)i * i; j < maxn; j += i) {
                f[j] = 1;
            }
        }
    }
}

bool isPrime(int x) {
    return !f[x];
}

int sumFourDivisors(int* nums, int numsSize){
    int i, j, p, q;
    int ans = 0;
    ethPrime();                                  // (1)
    for(i = 0; i < numsSize; ++i) {              // (2)
        for(j = 1; j <= primes[0]; ++j) {        // (3)
            p = primes[j];
            if(nums[i] % p == 0) {
                q = nums[i] / p;
                if( isPrime(q) && p != q) {
                    ans += (p+1)*(q+1);         // (4)
                }
                if( q == (long long)p * p ) {
                    ans += p*p*p + p*p + p + 1; // (5)
                }                
                break;
            }
        }
    }
    return ans;
}

• $(1)$ 基本上数论的题，都离不开
  素数筛选 批量判定区间内的素数 https://blog.csdn.net/WhereIsHeroFrom/article/details/120875259
  ；
• $(2)$ 枚举每个数 $x = nums[i]$；
• $(3)$ primes[0]记录了题目范围内的素数个数，枚举范围内的素数；
• $(4)$ 当一个数是 $x=pq$ 的形式，则它 因子和 为 $\frac {p^2-1}{p-1} \times \frac {q^2-1}{q-1}$；
• $(5)$ 当一个数是 $x = p^3$ 的形式，则它的 因子和 为 $\frac {p^4-1}{p-1}$；

  五、推荐专栏

  💜《夜深人静写算法》💜 夜深人静写算法（四十一）- 单调队列,夜深人静写算法（二）- 动态规划入门,夜深人静写算法（四十）- 八大排序,ACM,算法,搜索 https://blog.csdn.net/whereisherofrom/category_9273531.html
   
  （三）初等数论入门 简要介绍 初等数论 的基础内内容 https://blog.csdn.net/WhereIsHeroFrom/article/details/111693538

六、习题练习

序号	题目链接	难度
1	四因数 https://leetcode-cn.com/problems/four-divisors/	★★☆☆☆

《算法零基础100讲》(第12讲) 因子和_英雄哪里出来-CSDN博客 一个奇妙的方法求解因子和 https://blog.csdn.net/WhereIsHeroFrom/article/details/120875424