题解 P3912 【素数个数】

Ge_er · 2018-12-12 22:06:21 · 题解

此题代码其实很短！

核心思想：这题好水啊用bool筛选指质数

于是就有了这样的代码：

# include <cstdio>
# include <cstring>
using namespace std;

bool flag[100000001];

int main()
{
    memset (flag, false, sizeof(flag));
    int n;
    scanf ("%d", &n);
    int ans = n - 1;
    for (int i = 2; i <= n; i++)
        if (!flag[i])//若i是质数，那么i * j一定是合数
        {
            for (int j = 2; i * j <= n; j++)
                if (!flag[i * j])
                {
                    flag[i * j] = true;
                    ans--;
                }
        }
    printf ("%d\n", ans);
    return 0;
}

不过，这个代码运行起来有些慢，TLE也是正常的

问题出在这一行上：

for (int i = 2; i <= n; i++)

能否将它改为这样呢？

for (int i = 2; i * i <= n; i++)

这就相当于要证明：不大于 n 的任意一个合数的质因数中至少有一个在2 ～ sqrt(n)之间。

反证法：开始假正经合数的质因数都大于sqrt(n)

设该合数 S 可表示为 a[1] × a[2] × ... × a[k] (k >= 2)

则 S > sqrt(n) ^ k >= n

综上，S > n， 矛盾。

故可以把原代码改为 i * i <= n 。

所以，我们就有了

正解

# include <cstdio>
# include <cstring>
using namespace std;

bool flag[100000001];

int main()
{
    memset (flag, false, sizeof(flag));
    int n;
    scanf ("%d", &n);
    int ans = n - 1;
    for (int i = 2; i * i <= n; i++)
        if (!flag[i])
        {
            for (int j = 2; i * j <= n; j++)
                if (!flag[i * j])
                {
                    flag[i * j] = true;
                    ans--;
                }
        }
    printf ("%d\n", ans);
    return 0;
}

请各位dalao多多指教！