筛质数
1.埃氏筛法
#include <iostream>
#include <algorithm>
using namespace std;
const int N= 1000010;
int primes[N], cnt;
bool st[N];
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (st[i]) continue;
primes[cnt ++ ] = i;
for (int j = i + i; j <= n; j += i)
st[j] = true;
}
}
int main()
{
int n;
cin >> n;
get_primes(n);
cout << cnt << endl;
return 0;
}
2.线性筛法
#include <iostream>
#include <algorithm>
using namespace std;
const int N= 1000010;
int primes[N], cnt;
bool st[N];
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break; //pj一定是最小质因子
}
}
}
int main()
{
int n;
cin >> n;
get_primes(n);
cout << cnt << endl;
return 0;
}
题目:
Forsaken喜欢数论;
链接:https://ac.nowcoder.com/acm/problem/53079
来源:牛客网
题目描述
Forsaken有一个有趣的数论函数。对于任意一个数xx,f(x)f(x)会返回xx的最小质因子。如果这个数没有最小质因子,那么就返回0。
现在给定任意一个nn,Forsaken想知道\sum_{i = 1}^{n}{f(i)}∑
i=1
n
f(i)的值。
输入描述:
一个整数nn。
输出描述:
一个整数代表上面的求和式的值。
示例1
输入
4
输出
7
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=3e7+10;
long long int n;
int primes[N],cnt;
bool st[N];
void get_prime(int n)
{
long long int sum=0;
for (int i = 2; i <= n; i ++ )
{
if(!st[i]) primes[cnt++]=i,sum+=i;
for(int j=0;primes[j]<=n/i;j++)
{
st[primes[j]*i]=true;
sum+=primes[j];
if(i%primes[j]==0)
break;
}
}
printf("%lld",sum);
}
int main()
{
cin>>n;
get_prime(n);
return 0;
}