最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

算法3：质数的个数-全球观察

来源：博客园

一、质数的定义


(资料图)

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

二、判断质数的方法

1 for(int j = 2; j < i; j ++) {2     if(i % j == 0)3         break;4     if(i == j)5         cout << i << " ";6 }

三、完整代码

1 #include 2 using namespace std; 3   4 int main() { 5     int n, k = 0, count = 1; 6     //2直接输出  7     cin >> n; 8     printf("2 "); 9     for (int j = 2; j <= n; j++){10         for (int i = 2; i < j ; i++) {11             if (j % i == 0)12                 break;13             else if ((j % i != 0) && (i == (j-1)))14                 k = j;15             else16                 continue;17             count ++;18             printf("%d ", k);19         }                20     }21     printf("\n1-%d有%d个素数", n, count);22     return 0;23 }

四、优化

当我们的数据比较小的时候，我们当然可以使用双重循环的暴力做法找到质数，但是当数据较大时，时间复杂度会随之变大，我们可以通过sqet(n)进行第一次优化。

1 #include 2 using namespace std; 3  4 int main() { 5     int N, count = 0; 6     cin >> N; 7     for (int n = 1; n <= N; n ++) { 8         for (int i = 2; i <= sqrt(n); i ++) { 9             if (n % i == 0)10                 break;11         }12         if (j < i)13             printf("%d ", n);14             count ++;15     }16     printf("\n1-%d有%d个素数", N, count);17     return 0;18 }

埃氏筛

首先将2到n范围内的整数写下来。

其中2是最小的素数，将表中所有的2的倍数划去。

表中剩下的最小的数字就是3，他不能被更小的数整除，所以3是素数。

再将表中所有的3的倍数划去…… 以此类推，如果表中剩余的最小的数是m，那么m就是素数。

然后将表中所有m的倍数划去，像这样反复操作，就能依次枚举n以内的素数。

埃氏筛法的时间复杂度是0(n*log(logn))。

1 #include 2 using namespace std; 3 const int N = 1e8 + 10; 4 bool isprime[N]; 5  6 int main() { 7     int n, i, ans; 8     cin >> n; 9     for(int i = 0;i < N; i ++)10         isprime[i] = true;11 //     isprime[0] = false;12 //     isprime[1] = false;13     for(int i = 2; i <= n; i ++) {14         if(isprime[i]) {15             for(int j = i * 2; j <= n; j += i){16                 //筛掉前面素数的倍数17                 isprime[j] = false;18             }19         }20         if(isprime[i])21             ++ ans;22     }23     cout << ans;24     return 0;25 }

对于较大的数据，这个代码是不能AC的，我们需要进一步的优化。

1 #include 2 using namespace std; 3 bool a[100000005]; 4 int main() { 5     int n, ans = 0; 6     cin >> n; 7     for(int i = 2; i * i <= n; ++ i) { 8         if(a[i] == 0){ 9             for(int j = i * i; j <= n; j += i) {10             //这里直接j=i*i,而不用j=i*2;因为前面有2*i,3*i,4*i....,(i-1)*i11                 a[j] = 1;12             }13         }14     }15     for(int i = 2; i <= n; ++ i) {16         if(a[i] == 0)17             ++ ans;18     }19     cout << ans;20     return 0;21 }

欧拉筛（线性筛）

欧拉筛法的原理同埃氏筛法，多了一个判断删除与标记最小质因子的过程。

在埃氏筛法中，一个合数来说可能会被筛多次，比如6可以被2筛去，也可以被3筛去，而欧拉筛要做的事情就是让一个合数只被筛一次。

首先，任何合数都能表示成多个素数的积。所以，任何的合数肯定有一个最小质因子。我们通过这个最小质因子就可以判断什么时候不用继续筛下去了。

首先看核心代码：

1 void ola(int n) 2 { 3     for (int i = 2; i <= n; i ++ ) 4     { 5         if (st[i] == 0) primes[cnt ++ ] = i;//将质数存到primes中 6         for (int j = 0; primes[j] <= n / i; j ++ )//要确保质数的第i倍是小于等于n的。 7         { 8             st[primes[j] * i] = 1; 9             if (i % primes[j] == 0) break;10         }11     }

再看完整代码：

1 #include 2 using namespace std; 3  4 int v[100001000]; //v[i]=a代表数i的最小质因数为a  5 int prime[600000];  6 int cnt = 0; 7   8 void is_prime(int n) { 9     v[0] = v[1] = 1;10     for(int i = 2; i <= n; ++ i) { //注意这里也统计了等于n的数 11         if(! v[i]){ 12             v[i] = i;13             prime[++ cnt] = i;14         } 15         for(int j = 1; j <= cnt; ++ j) {16             if(prime[j] > n / i || prime[j] > v[i])17                 break; 18             v[i * prime[j]] = prime[j];19 20         }21     }22 } 23  24 int main(){25     int n, q;26     cin >> n >> q;27     is_prime(n);28     for(int i = 0; i < q; ++ i) {29         int k;30         cin >> k;31         cout << prime[k] << endl;32     }33     return 0;34 }

关键词：