题解 | #区间素数求和#

埃氏筛法

昨天提交还是只通过90%，今天提交就过了，我也很迷

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int n=1e6+5;
long long vis[n],prime[n];
int main()
{
	/*
	先假设所有的数都是素数
	0和1不是素数，标记出来
	接着，从2开始遍历，所有素数的倍数必然是合数，而所有合数的倍数也必然是合数
	把遍历到的数的倍数都标记出来，那么合数就都被标记了 
	唯一缺陷就是，会存在重复标记，因为一个合数很可能有两个质因子 
	*/
    long long t,l,r,s=0,i,j,cnt=0;
        cin>>t;
    	memset(vis,0,sizeof(vis)); //假设所有的数都是素数
    	vis[0] = vis[1] = 1;  //0 和 1不是素数
    	for (i = 2; i <n; i++)
        	if (!vis[i]) {         //如果i是素数，让i的所有倍数都不是素数
            	prime[cnt++]=i;//存储所有的素数 
            	for (j = i*i; j <n; j += i) 
                	vis[j] = 1;
        	} 
    while(t--){
    	cin>>l>>r;
        s=0;
        for(i=0;prime[i]<=r;i++) 
             if(prime[i]>=l) s+=prime[i];
    	cout<<s<<endl;
	}
 } 
 
 

这是之前的代码，过了90%的那个，好像就只是因为宏常量的原因，，，

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long vis[1000010],prime[1000010];
int main()
{
	/*
	先假设所有的数都是素数
	0和1不是素数，标记出来
	接着，从2开始遍历，所有素数的倍数必然是合数，而所有合数的倍数也必然是合数
	把遍历到的数的倍数都标记出来，那么合数就都被标记了 
	唯一缺陷就是，会存在重复标记，因为一个合数很可能有两个质因子 
	*/
    long long t,l,r,cnt=0,s=0,i,j;
        cin>>t;
    	memset(vis,0,sizeof(vis)); //假设所有的数都是素数
    	vis[0] = vis[1] = 1;  //0 和 1不是素数
    	for (i = 2; i <1000001; i++)
        	if (!vis[i]) {         //如果i是素数，让i的所有倍数都不是素数
            	prime[cnt++]=i;//存储所有的素数 
            	for (j = i*i; j <1000001; j += i) 
                	vis[j] = 1;
        	} 
    while(t--){
    	cin>>l>>r;
        s=0;
        for(i=0;prime[i]<=r;i++) 
             if(prime[i]>=l) s+=prime[i];
    	cout<<s<<endl;
	}
 } 

欧拉筛(到底还是要比埃氏筛法快一些)

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int n=1e6+5;
long long vis[n],prime[n];
int main()
{
    long long t,l,r,s=0,i,j,cnt=0;
        cin>>t;
    	memset(vis,0,sizeof(vis)); //假设所有的数都是素数
    	vis[0] = vis[1] = 1;  //0 和 1不是素数
    	for (i = 2; i <n; i++){//i的初始值必须是2，不能是1
        	if (!vis[i])         //如果i是素数，让i的所有倍数都不是素数
            	prime[cnt++]=i;//存储所有的素数 
            for (int j = 0; j <cnt&& i*prime[j] <= n; j++){
                vis[i*prime[j]] = 1;
                if (i % prime[j] == 0) break;
            }
        } 
    while(t--){
    	cin>>l>>r;
        s=0;
        for(i=0;prime[i]<=r;i++) 
             if(prime[i]>=l) s+=prime[i];
    	cout<<s<<endl;
	}
 } 
 
 

关于for (int j = 0; j <cnt&& iprime[j] <= n; j++) vis[iprime[j]] = 1; 的解释

解释一：
prime[j]是当前已经确定的素数，而i*prime[j]计算的该素数的倍数 

	此前有一点疑惑， i是外层循环的控制变量，有可能轮到这个素数的时候，
i已经>2、3、4、5。。。了，就没办法计算这个素数的 2、3、4、5。。。倍了。

但是其实是这样的：
	如果该素数前有素数，那么其实这两个素数的倍数已经被标记为合数了，作为（比prime[j]小的
素数）的倍数被标记了 

解释二： 

	我们之前做埃氏筛法的优化时就已经知道了，循环标记时j的下标应该从i*i开始，原因见《计算机考
研机试指南 》P96，而在这里，我们得到一个新的素数的时候，prime[j]是通过i赋值给它得到的，
那么其实i*prime[j]的初始值就相当于i*i ，也因此i是不会小于prime[j]的，也即i>=prime[j] 永真

	i如果是素数，那么i=prime[j]的最大值
	i如果是合数，那么i>prime[j]的最大值 

《计算机考研机试指南 》P96

关于 if (i % prime[j] == 0) break;的解释

	j是从小到大的， 那么prime[j]也是从小到大的，prime[j]里面存的都是素数，那么i对prime[j]
求余能除尽，说明prime[j]是i的质因子,那么i对prime[j]求余，遇到的第一个能除尽的数就是i的最
小质因子