素数个数
今天这都什么破题啊……
首先是统计素数个数的破题
这是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\n",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的我改题都懒得改,原题都懒得放