WHCSRL 技术网

【跟着英雄学算法第⑫讲】因子和——附Leercode刷题题解(C语言实现)三种解法

✨前言✨

       在这个系列中,博主准备分享每日在万人千题社区打卡学习的算法。博主也是小白,因此也很能理解新手在刷题时的困惑,所以关注博主,每天学习一道算法吧。同时也欢迎大家加入万人千题习活动,正所谓:一个人可以走的很快,但一群人才能走的更远。

万人千题社区https://bbs.csdn.net/forums/hero?category=0icon-default.png?t=L9C2https://bbs.csdn.net/forums/hero?category=0


目录

一、素数知识回顾

二、算法思想笔记

三、1390.四因数

 ①题目呈现

 ②代码操练1

 ③代码操练2

​ ④代码操练3 


 

一、素数知识回顾

①素数判定:枚举 i * i <= num的所有情况

②算数基本定理:每一个整数都可以唯一分解成几个素数的乘积

③素数筛选与分解:枚举法,埃氏筛,欧拉筛……

④因子数:

 二、算法思想笔记

以n=2*2*2*3*3来说明:(2^0 + 2^1 +2^2 +2^3)* (3^0 + 3^+ 3^2)

每当确定一个2的取法,3的取法都是相同的,都有以上三种。因此根据乘法分配律可以结合成上述形式。

三、1390.四因数

四因数icon-default.png?t=L9C2https://leetcode-cn.com/problems/four-divisors/submissions/

①题目呈现

 ②代码操练1(英雄的解法,唯一与本专题相关)🙃

  1. #define maxn 100001
  2. #define ll long long
  3. bool f[maxn];
  4. int primes[maxn];//prime[0]相当于计数器的作用
  5. void ethPrime(){
  6. int i;
  7. ll j;
  8. f[0] = f[1] = 1;
  9. primes[0] = 0;
  10. for(i = 2; i < maxn; ++i) {
  11. if(!f[i]) {
  12. primes[++primes[0]] = i;
  13. for(j = (ll)i * i; j < maxn; j += i) {
  14. f[j] = 1;
  15. }
  16. }
  17. }
  18. }
  19. bool isPrime(int x) {
  20. return !f[x];
  21. }
  22. int sumFourDivisors(int* nums, int numsSize){
  23. int i, j, p, q;
  24. int ans = 0;
  25. ethPrime(); // (1)
  26. for(i = 0; i < numsSize; ++i) { // (2)
  27. for(j = 1; j <= primes[0]; ++j) { // (3)
  28. p = primes[j];
  29. if(nums[i] %% p == 0) {
  30. q = nums[i] / p;
  31. if( isPrime(q) && p != q) {
  32. ans += (p+1)*(q+1); // (4)
  33. }
  34. if( q == (long long)p * p ) {
  35. ans += p*p*p + p*p + p + 1; // (5)
  36. }
  37. break;
  38. }
  39. }
  40. }
  41. return ans;
  42. }

分析: 

1.根据之前所学的因子数知识和算数基本定理,我们得出有四个因子只有两种情况

1)两个素数的乘积         2)一个素数的三次方

2.ethPrime()函数用埃氏筛标记处于2~maxn之间所有的质数,便于我们之后求解

3.ans计算和判断原因见下图

 

结果: 

 

 ③代码操练2

  1. int sumFourDivisors(int* nums, int numsSize)
  2. {
  3. int total = 0;
  4. int j = 0;
  5. int i = 0;
  6. for( i = 0; i < numsSize ; i++)
  7. {
  8. int cnt = 0;
  9. int sum = 0;
  10. for( j = 1; j*j < nums[i]; j++)
  11. {
  12. if(nums[i] %% j == 0)
  13. {
  14. cnt++;
  15. sum += j + nums[i] / j;
  16. }
  17. }
  18. if(cnt == 2 && j * j != nums[i])
  19. {
  20. total += sum;
  21. }
  22. }
  23. return total;
  24. }

分析: 

 枚举法yyds,就不用我多说了吧。

结果: 

 ④代码操练3 

  1. #define maxn 100005
  2. bool f[maxn]={0};//标记对应下标数是否为变量
  3. int prime[maxn]={0};
  4. void prime_list()
  5. {
  6. f[1] = 1;
  7. prime[0]=0;
  8. for (int i = 2; i <= 1E5; i++)//欧拉筛
  9. {
  10. if (!f[i])
  11. {
  12. prime[++prime[0]] = i;
  13. }
  14. for (int j = 1; i * prime[j] <= 1E5; j++)
  15. {
  16. f[i * prime[j]] = 1;
  17. if( i %% prime[j] == 0)
  18. break;
  19. }
  20. }
  21. }
  22. int sumFourDivisors(int* nums, int numsSize)
  23. {
  24. prime_list();
  25. int total = 0;
  26. for (int i = 0; i < numsSize; i++)
  27. {
  28. int cnt = 0;
  29. for (int j = 1; prime[j]*prime[j] < nums[i] ; j++)
  30. {
  31. if (nums[i] %% prime[j] == 0 && !f[nums[i] / prime[j]])
  32. {
  33. total += nums[i] + 1 + prime[j] + nums[i] / prime[j];
  34. break;
  35. }
  36. else if (nums[i] %% prime[j] == 0 && pow(prime[j], 3) == nums[i])
  37. {
  38. total += 1 + prime[j] + prime[j] * prime[j] + prime[j]*prime[j]*prime[j];
  39. break;
  40. }
  41. }
  42. }
  43. return total;
  44. }

分析:

解释一下内循环j的判断理由:

如果prime[j] 是nums[i]的质数,因为题目要求是四质数,则nums[i]/prime[j]必定为质数,否则合数可以再分成质数,结果就不会是四质数。

结果:

上面的代码希望对你有所帮助。有优化建议希望可以在下方留言

推荐阅读