题目链接 题意：题解： AC代码 #include<bits/stdc++.h>
using namespace std;
const int N = 3e7 + 10;
int prime[N];
int miniFactor[N];
int primepos;
void
展开全文
把筛法改一改就行了 最先到的就是最小质素因子 #include <bits/stdc++.h>
#define ll long long
using namespace std;
int const N=3e7+5;
ll p[N],ans,n;
int main()
{
ci
展开全文
Forsaken喜欢数论 题目地址： https://ac.nowcoder.com/acm/problem/53079 基本思路： 其实就是一个素数筛，我们想一下在埃氏筛法的过程中，我们是从小到大的对于每个质数，将它的倍数都筛掉，那么这个质数其实就是这些被筛掉的非质数的质因子，并且由于我们
展开全文
https://ac.nowcoder.com/acm/problem/53079题意：给定一数n，求1~n每个数的最小质因数的和。 分析：可以用欧拉线性筛素数法，每个数仅使用其最小素因数筛去，开始先打个表，后面直接统计答案就行了。 代码： #include<stdio.h>
#incl
展开全文
欧拉筛
题解
欧拉筛
欧拉筛法可以在线性的时间复杂度里筛出N以内的所有质数
vector<long long> oula(long long n)
{
vector<long long> prime;
vector<bool> vis(n + 1
展开全文
这道题需要了解素数筛的原理，而不是只是套模板。需要明白一点，我们在欧拉筛中筛掉合数用的是这个合数的最小值因子。还记得那一步if(i%primes[j]==0) break;吗？这一步就保证我们用的是最小值因子筛掉所有的合数。我们可以这么理解，当i%primes[j]的时候，i=k*primes[j]
展开全文
题目描述 Forsaken有一个有趣的数论函数。对于任意一个数x，f(x)会返回x的最小质因子。如果这个数没有最小质因子，那么就返回0。 现在给定任意一个n，Forsaken想知道 。 输入描述:一个整数n。 输出描述:一个整数代表上面的求和式的值。 思路：线筛的一道题。
展开全文
寻找1-n最小的质因数相加，最直接的暴力就是从素数表中找到最小因数，联想到素数筛的过程可以直接找到最小质因数。这里要注意的点是：理论上3e7是不会爆int的，但是在for(long long j=ii;j<=n;j+=i)这句中，ii会爆int，导致出错。 #include<iostre
展开全文
题目 对于任意一个数 ，会返回 的最小质因子。如果这个数没有最小质因子，那么就返回 0。现在给定任意一个 ，求 的值。 解题思路 在从 1 到 遍历整数时，使用筛法求素数。如果本身是素数，那么它本身就是它的最小质因子，累加计入 。遍历由该素数生成的合数，如果还没访问过，表示这个合数的最小质因子
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
