一、质数的定义
质数是指在大于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<bits/stdc++.h> 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 else 16 continue; 17 count ++; 18 printf("%d ", k); 19 } 20 } 21 printf("\n1-%d有%d个素数", n, count); 22 return 0; 23 }
四、优化
当我们的数据比较小的时候,我们当然可以使用双重循环的暴力做法找到质数,但是当数据较大时,时间复杂度会随之变大,我们可以通过sqet(n)进行第一次优化。
1 #include<bits/stdc++.h> 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<iostream> 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<bits/stdc++.h> 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)*i 11 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<iostream> 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 }
标签:prime,int,质数,个数,cin,算法,using,include From: https://www.cnblogs.com/wanyy-home/p/17367121.html