2025年7月26日训练日志

2523. 范围内最接近的两个质数 - 力扣（LeetCode）

简单模拟+线性素数筛

class Solution {
public:vector<int> closestPrimes(int left, int right) {int n = right + 1;vector<int>is(n,1);is[0] = 1;queue<int>q;int res = INT_MAX;int last = -1;for(int i=2;i<n;i++){if(is[i]){if(i>=left && i<=right){if(q.size()==2){int cnt = q.back() - q.front();if(i-last < cnt){q.pop();q.pop();q.push(last);q.push(i);}res = min(res,cnt);}if(q.size()<2){q.push(i);}last = i;}if((long long)i*i<n){for(int j=i*i;j<n;j+=i){is[j] = 0;}}}}vector<int>ans;if(q.size()==2){while(!q.empty()){ans.push_back(q.front());q.pop();}return ans;}else{return {-1,-1};}}
};

 2521. 数组乘积中的不同质因数数目 - 力扣（LeetCode）

 分解质因数，可以直接对因数进行分解，不用乘了再进行分解

class Solution {
public:int distinctPrimeFactors(vector<int>& nums) {unordered_set<int>st;for(int num : nums){int x = num;for(int i=2;i*i<=x;i++){while(x % i == 0){st.insert(i);x /= i;}}if(x > 1) st.insert(x);}return st.size();}
};

2507. 使用质因数之和替换后可以取到的最小值 - 力扣（LeetCode）

 暴力

class Solution {
public:int smallestValue(int n) {int sum = n;int prev;do {n = sum;prev = n;sum = 0;int temp = n;for (int i = 2; i * i <= temp; i++) {while (temp % i == 0) {sum += i;temp /= i;}}if (temp > 1) sum += temp;} while (prev != sum);return sum;}
};

172. 阶乘后的零 - 力扣（LeetCode）

 题目要求找阶乘后的0的数量，能产生0的质因子就只有2和5，缺一不可，因此那就对n到1计算质因数，然后取2和5的最小数

class Solution {
public:int trailingZeroes(int n) {vector<int>a(10005,0);for(int u=2;u<=n;u++){int num = u;for(int i=2;i*i<=num;i++){while(num%i==0){a[i]++;num/=i;}}if(num>1) a[num]++;}return min(a[2],a[5]);}
};