问题描述：
乌拉拉喜欢素数，最新的一项意大利研究发现，每天做3道数学题，会使人目达耳通，秀外慧中，颖悟绝伦，七窍玲珑。一天，乌拉拉在研究素数的时候发现，所有 n>5 的素数个位数一定是1，3，7，9中的一个。于是，乌拉拉想统计一下在小于等于n的正整数里，有多少个位数为1，3，7，9的正整数是素数
输入：
一个正整数n。 (1 < n <= 1000000)
输出：
两个整数a，b。分别是个位数是1，3，7，9的正整数的数量 a 和 其中素数的个数 b
样例输入：
10
样例输出：
4 2
原因分析：
两种方法：1.用根号（缩小循环次数，防止超时）判断是否为素数 不再介绍
2.欧拉素数筛选法.
解决方案：
先上AC代码：
#include<bits/stdc++.h>
using namespace std;
int n,vi[1000005],su[1000005],cnt=0,a=1,b=0;int main(void)
{scanf("%d",&n);for(int i=2;i<=n;i++){if(i%10==1||i%10==3||i%10==7||i%10==9)a++;if(vi[i]==0){su[cnt++]=i;if(i%10==1||i%10==3||i%10==7||i%10==9)b++;}for(int j=0;j<cnt&&i*su[j]<=n;j++){vi[i*su[j]]=1;if(i%su[j]==0)break;}}printf("%d %d",a,b);return 0;
}
欧拉素数筛选法：
n为一个要求的范围中的最大值，vi数组拿来判断是否被划去，su数组拿来存素数，cnt正好等于素数的个数
#include<bits/stdc++.h>
using namespace std;
int n,vi[1000005],su[1000005],cnt=0;int main(void)
{scanf("%d",&n);for(int i=2;i<=n;i++){if(vi[i]==0) //若没被划去，则存入su数字组；{su[cnt++]=i;}for(int j=0;j<cnt&&i*su[j]<=n;j++){vi[i*su[j]]=1; //划去su[j]*i的数 比如su[0]=2,则划去2*2=4 4不是素数if(i%su[j]==0)break; //下面细锁}}return 0;
}
正题：
大体思路：根据这个i%su[j]==0条件推出 i*su[j+1]=1 是不应该进行的（即后面 也 存在将
vi[ i*su[j+1] ]=1 这个操作，即重复划去同一个数，浪费时间）
过程：
i%su[j]==0 推出 i=k*su[j] 然后如果接着进行，不中断循环（根据上面我们知道会造成
vi[ i*su[j+1] ]=1 重复划去该数） i*su[j+1]=k*su[j]*su[j+1]=( k*su[j+1] )*su[j] 继而推出 i*su[j+1]为 su[j]的 k*su[j+1] 倍
即 如果循环接着进行（i一直变大），当i=k*su[j+1]时，su[j]* 这个i，即等于前面（i未变大时候）的 i*su[j+1] 又会重新划去该数，划了两次 .所以为了防止这种情况，要在第一次中断内存循环 if(i%su[j]==0) break； 继而在下一次再把 i*su[j+1] 该数划去
题外话：
翻了好多大佬博客，全部看了看，自己举了举例，花了三四个小时才搞明白，泪目.