前言
原文出自：演算法零基礎100講
目錄
- 前言
- LeetCode 1390.四因數
- 分析
- 方法
- 因子和公式
- 代碼
LeetCode 1390.四因數
原題鏈接：1390.四因數
分析
根據題目要求得出，如果一個數滿足有四個因數，那除去 1和數字本身，就剩下兩個素數的乘積，所以有以下兩種情況：
1.兩個素數的乘積，即 num = p*q;
2.某個素數的三次冪， 即 num = p×p×p；
方法
- 首先要篩選出題目范圍內所有的素數，文章采用的篩選方法為埃氏篩，
- 遍歷陣列，對每個數字num, 在[2, sqrt(num)]范圍內的素數進行試除；
- 如果數字num能夠分解為兩個素數，或一個素數的三次冪，則使用因子和公式，求出因子和，
因子和公式
出處：英雄哪里出來
專欄：《演算法零基礎100講》
如果該資料num可由兩個素數相乘得到，即 num = p*q，則因子和公式為：
如果該資料num是由一個素數的三次冪得到，即num = p×p×p，則因子和公式為：
代碼
#define maxn 100001
#define ll long long
//全域陣列默認初始化為0
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();
for (i = 0; i < numsSize; ++i) //遍歷傳進來的陣列
{
//遍歷素數，primes[0]中存放的素數個數
for (j = 1; j <= primes[0]; ++j)
{
p = primes[j];
if (nums[i] % p == 0)
{
q = nums[i] / p;
if (isPrime(q) && p != q)
{
ans += (p + 1) * (q + 1);
}
if (q == (long long)p * p)
{
ans += p * p * p + p * p + p + 1;
}
break;
}
}
}
return ans;
}
個人感覺大哥用的方法，是非常聰明，還能幫助我們鞏固一下基礎知識，非常贊👍，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/344139.html
標籤：其他
上一篇：程式媛的秋招總結