AcWing 868. 筛质数怎么改写成长尾词呢？
- 内容介绍
- 文章标签
- 相关推荐
本文共计352个文字，预计阅读时间需要2分钟。
题目：给定一个正整数 $n$，请求出 $1^2 + 2^2 + \ldots + n^2$ 的和。
输入格式：共一行，包含一个整数 $n$。
输出格式：共一行，包含一个整数，表示 $1^2 + 2^2 + \ldots + n^2$ 的和。
数据范围：$1 \leq n \leq 10^6$。
输入样例：
100
输出样例：
338350
题目
给定一个正整数 $n$，请你求出 $1∼n$ 中质数的个数。
输入格式 共一行，包含整数 $n$。
输出格式 共一行，包含一个整数，表示 $1∼n$ 中质数的个数。
数据范围 $1≤n≤10^6$ 输入样例：
8
输出样例：
4
思路
- 朴素筛选 遍历到某个数值 $i$ 我们将它的倍数全部删除，如此反复，剩下的为 $1∼n$ 中的所有质数
代码
朴素筛选法
#include <iostream>
using namespace std;
const int N = 1000010;
int n, primes[N];
bool st[N];
int find_primes(int x)
{
int cnt = 0;
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = i; j <= n; j += i) st[j] = true;
}
return cnt;
}
int main()
{
cin >> n;
cout << find_primes(n) << endl;
return 0;
}
本文共计352个文字，预计阅读时间需要2分钟。
题目：给定一个正整数 $n$，请求出 $1^2 + 2^2 + \ldots + n^2$ 的和。
输入格式：共一行，包含一个整数 $n$。
输出格式：共一行，包含一个整数，表示 $1^2 + 2^2 + \ldots + n^2$ 的和。
数据范围：$1 \leq n \leq 10^6$。
输入样例：
100
输出样例：
338350
题目
给定一个正整数 $n$，请你求出 $1∼n$ 中质数的个数。
输入格式 共一行，包含整数 $n$。
输出格式 共一行，包含一个整数，表示 $1∼n$ 中质数的个数。
数据范围 $1≤n≤10^6$ 输入样例：
8
输出样例：
4
思路
- 朴素筛选 遍历到某个数值 $i$ 我们将它的倍数全部删除，如此反复，剩下的为 $1∼n$ 中的所有质数
代码
朴素筛选法
#include <iostream>
using namespace std;
const int N = 1000010;
int n, primes[N];
bool st[N];
int find_primes(int x)
{
int cnt = 0;
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = i; j <= n; j += i) st[j] = true;
}
return cnt;
}
int main()
{
cin >> n;
cout << find_primes(n) << endl;
return 0;
}