素数个数

今天这都什么破题啊……

首先是统计素数个数的破题

这是zrt讲的线性筛法

 1 //O(n)
 2 // mindiv 一个数字的最小素因子
 3 // prime  
 4 for(int i=2;i<=n;i++){
 5     if(!mindiv[i]){    //没有就存为自己 
 6         mindiv[i]=i;
 7         prime[tot++]=i;    //判断为素数 
 8         //printf("%d ",i);
 9     }
10     for(int j=0;prime[j]*i<=n;j++){    //去掉不是素数的
11         mindiv[prime[j]*i]=prime[j]; // prime[j]<=mindiv[i]
12         //printf("# %d=%d*%d
",i*prime[j],i,prime[j]);
13         if(prime[j]==mindiv[i]) break;    //后面的就不用了，免得重复 
14     }
15 }
16 // N = p1^a1 p2^a2 p3^a3 ....
17 // 1) a1 == 1 i= p2^a2 p3^a3 .... prime[j] = p1
18 // 2) a1 >1  i=p1^(a1-1) p2^a2 p3^a3 .... prime[j] = p1
19 // O(n)

听有人说线性筛法好像不行（

反正我不知道（

这是正解给出的代码

 1 #include <cstdio> 
 2 #include <cstring> 
 3 #include <iostream>
 4 using namespace std;  
 5   
 6 bool isPrime[60000001];    //是不是素数 
 7 int primeCount, primes[5761455];    //存储素数 
 8    
 9 int main() {
10    freopen("prime.in","r",stdin);
11    freopen("prime.out","w",stdout); 
12     int n; 
13     scanf("%d",&n);
14     memset(isPrime, true, sizeof(isPrime));    //其实不这样也能做，不过有点别扭（ 
15     primeCount = 0; 
16     for (int i = 2; i <= n; ++ i) { 
17         if (isPrime[i]) { 
18             primes[primeCount ++] = i; 
19         } 
20         for (int j = 0; j < primeCount && i * primes[j] <= n; ++ j) { 
21             isPrime[i * primes[j]] = false; 
22             if (i % primes[j] == 0) {    //同线性筛法，防止重复 
23                 break; 
24             } 
25         } 
26     } 
27     printf("%d",primeCount); 
28     return 0; 
29 }

下面这个是……这是我写的暴力……

1 //我为什么要把我的破代码贴上来？

顺便说一句这个是老师让我们画的奇怪的图，我不想画，所以

mmp的我改题都懒得改，原题都懒得放