100分 #include <万能头文件> using namespace std; const int MAXN=10000000; bool isprime[MAXN]; int prime[MAXN],n,cnt; void euler(int n) { memset(isprime,true,sizeof(isprime)); isprime[1]=false; for(int i=2;i<=n;++i) { if(isprime[i]) prime[++cnt]=i; for(int j=1;j<=cnt&&iprime[j]<=n;++j) { isprime[iprime[j]]=false; if(i%prime[j]==0) break; } } } int main() { cin>>n; euler(n); cout<<cnt; return 0; }

题目虽然做出来了，但是有几个问题没搞明白：

1. 在定义数组的时候用int a[10000005]={0}会报错segment 11 用vector就没事。
2. 同样的代码vector<int>消耗内存是34M，但是vector<bool>只有1.6M。怎么会差那么多？

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> not_prime(n + 1, 0);
    for (int i = 3; i <= sqrt(n); i += 2) {
        if (not_prime[i]) continue;
        for (int j = i * i; j <= n; j += 2 * i) not_prime[j] = 1;
    }
    cout << (n + 1) / 2 - accumulate(not_prime.begin(), not_prime.end(), 0) << endl;
}

此题考查对质数判断的理解和优化方法：

方法一代码：60分

#include <bits/stdc++.h>
using namespace std;

bool prime(int x)
{
	for(int i=2; i<x; i++)
		if(x%i==0)
			return false;
	return true;
}

int main()
{
	int n,ans = 0;
	cin >> n;
	for(int i=2; i<=n; i++)
	{
		if(prime(i))
			ans++;
	}
	cout << ans;
	return 0;
}

方法二代码：70分

#include <bits/stdc++.h>
using namespace std;

bool prime(int x)
{
	for(int i=2; i*i<x; i++)
		if(x%i==0)
			return false;
	return true;
}

int main()
{
	int n,ans = 0;
	cin >> n;
	for(int i=2; i<=n; i++)
	{
		if(prime(i))
			ans++;
	}
	cout << ans;
	return 0;
}

方法三代码：90分

#include <bits/stdc++.h>
using namespace std;

bool prime(int x)
{
	if(x==2||x==3) return true;
	if(x%6!=1&&x%6!=5) return false;
	for(int i=5; i*i<=x; i+=6)
		if(x%i==0||x%(i+2)==0) return false;
	return true;
}

int main()
{
	int n,ans = 0;
	cin >> n;
	for(int i=2; i<=n; i++)
	{
		ans+=prime(i);
	}
	cout << ans;
	return 0;
}

方法四：100分，筛法，不做要求，感兴趣可以研究一下

#include <bits/stdc++.h>
using namespace std;
const int N = 1e7+5;
int n,ans;

bool isprime[N];
void getprime()
{
	memset(isprime,1,sizeof(isprime));
	isprime[0]=isprime[1]=0;
	for (int i=2; i<N; i++)
	{
		if (isprime[i])
		{
			for (int j=i*2; j<=N; j+=i)
				isprime[j]=0;
		}
	}
}
int main()
{
	getprime();
	cin >> n;
	for (int i=1; i<=n; i++)
		ans+=isprime[i]; 
	cout<<ans;
	return 0;
}

筛法，简单（2的倍数删了、3的倍数删了……）

AC代码！！

#include <iostream>
using namespace std;
int n,l;
bool f[10000005];
int main()
{
    cin >> n;
    for (int i = 2;i <= n;i++)
    {
        if (!f[i])
        {
            l++;
            if (i * i <= n)
            {
                for (int j = i;j <= n;j += i)
                {
                    f[j] = true;
                }
            }
        }
    }
    cout << l;
}

内存过大？讲一个神器，bitset，bitset 就是通过固定的优化，使得一个字节的八个比特能分别储存 8 位的 0/1。 bitset很像bool类型的数组，所以存的内容要么是true要么是false 对于一个 4 字节的 int 变量，在只存 0/1 的意义下，bitset 占用空间只是其1/32，计算一些信息时，所需时间也是其1/32。

const int N=1e7+5;
bitset<N> vis;
int n,ans;
void prime() 
{
	vis.set();
	vis[0]=vis[1]=0;
	for (int i=2;i*i<=n;i++) 
	{
	    if (vis[i]) 
		{
	      	for (int j=i<<1; j<=n; j+=i) vis[j] = 0;
	    }
	}
	for(int i=2;i<=n;i++)
	{
		if(vis[i]) ans++;
	}
}

#include <iostream>
using namespace std;
int n,cnt=0;
bool book[10000001];
int main(){
    cin>>n;
    for(int i=2;i<n;i++)for(int j=i*2;j<=n;j+=i)book[j]=true;
    for(int i=2;i<=n;i++)if(!book[i])cnt++;
    cout<<cnt<<endl;
    return 0;
}

一开始不知道为什么错了，结果发现是i也许是质数

Python代码

先上AC代码：

def count_primes(n):
    primes = [True] * (n + 1)   # 创建一个长为n+1的列表，里面全是True，表示0到n的每个数字是否为质数，列表的下标就代表那个数
    primes[0] = primes[1] = False   # 0和1不是质数
    for i in range(2, int(n**0.5) + 1):   # 遍历2至sqrtn，包括sqrtn, 提示里面有讲"而小于sqrtx的整数已经在2到sqrtx的整数试过了，因为就没有必要再试（sqrtx, x)范围内的数了"
        if primes[i]:  # 看列表当前的数字是否为True,是True就表示这个数是质数，用它进行筛法
            primes[i ** 2: n + 1: i] = [False] * len(primes[i ** 2: n + 1: i])   # 筛法
    return sum(primes)  # sum(primes)可以统计primes中所有True的数量，因为True是1，False是0

n = int(input())
print(count_primes(n))

为什么是primes[i ** 2: n + 1: i] = [False] * len(primes[i ** 2: n + 1: i])呢？ 这涉及到python的切片操作，众所周知list[a：b：c]表示从list[a]到list[b-1](因为切片包头不包尾）这一段中从list[a]开始每隔c个元素取一次元素，那么从$i^2$开始，每隔i取出的元素一定是i的倍数，又因为上一行if的限制，i是质数，那么i的倍数就是合数，所以这一行代码就是在说“将$i^2$到n的所有合数标记为False”.另外，$a^\tfrac{1}{n} = \sqrt[n]a$,所以代码中用n**0.5表示sqrtn.（好像是初二内容？）