素数

质数：

若一个正整数无法被除了1和它自身之外的任何自然数整除，则该数称为质数，否则称为合数。

质数的三种求法中，筛选法优选线性筛法，判定则用试除法最好。

试除法：

 1 #include<iostream>
 2 using namespace std;
 3 int n;
 4 bool is_prime(int x){
 5     if(x <= 1) return 0;
 6     for (int i=2; i*i<=x; i++)
 7         if (x % i == 0) return 0; 
 8     return 1;
 9 } 
10 int main(){
11     cin >> n;
12     for (int i=1; i<=n; i++)
13         if (is_prime(i)) cout << i <<"
";
14     
15     return 0;
16 }

Eratosthenes筛法：

 1 #include<iostream>
 2 using namespace std;
 3 int n, num;
 4 bool flag[100000];
 5 void Eratosthenes(int n){
 6     for(int i=2; i*i<=n; i++){
 7         if(flag[i]) continue;
 8         for(int j=i*2; j<=n; j+=i)
 9             flag[j] = 1;
10     }
11 }
12 int main(){
13     cin >> n;
14     Eratosthenes(n);
15     for(int i=1; i<=n; i++)
16         if(!flag[i]) cout << i <<"
";
17     
18     return 0;
19 }

线性筛法：

 1 #include<iostream>
 2 using namespace std;
 3 int prime[100000], num, n;
 4 bool flag[100000];
 5 void primes(int n){
 6     for(int i=2; i<=n; i++){
 7         if(!flag[i]) prime[++num] = i;
 8         for(int j=1; j<=num; j++){
 9             if(prime[j] * i > n) break;
10             flag[prime[j] * i] = 1;
11             if(prime[j] % i == 0) break;
12         }
13     } 
14 }
15 int main(){
16     cin >> n;
17     primes(n);
18     for(int i=1; i<=num; i++){
19         cout << prime[i] <<"
";
20     }
21     return 0;
22 }