c++实现筛除法求素数和分解质因数_用指针筛素数的代码c++

关于代码中的maxn变量，它实际上是和输入的n是同一量级，或者说直接可以等于n；但和普通素数求法一样，sqrt（n）就可以解决问题。
知识点一：
筛除法原理：若n为素数，那他的n$\times$ 2，n$\times$ 3等等，就都不是素数，在之后的筛查就直接跳过。至于为何从j $\times$ j开始，是因为从j $\times$ 2开始，会有好多数重复计算。
知识点二：
vector变量做形参。有两种形式
1.地址形式，除在形参处加地址符外别无区别，见最终代码。
2.指针形式，形参处加指针符号*，实参处传地址&，使用时要用指针操作->

void initial(vector<int>*prime){
	bool isPrime[200];
	for(int i = 0;i<n;i++){
		isPrime[i] = true;
	}
	isPrime[0] = false;
	isPrime[1] = false;
	for(int j = 2;j<n;j++){
		if(!isPrime[j])
			continue;
		prime->push_back(j);//只能用指针操作
		for(int k = j*j;k<n;k += j){
			isPrime[k] = false;
		}
	}
}
int main(){
	vector<int>prime;
	initial(&prime);
	......
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

最终代码，形参形式

#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>

using namespace std;

const int maxn = sqrt(1e4) +1;

void initial(vector<int>&prime){
	bool isPrime[maxn];
	for(int i = 0;i<maxn;i++){
		isPrime[i] = true;
	}
	isPrime[0] = false;
	isPrime[1] = false;
	for(int j = 2;j<maxn;j++){
		if(!isPrime[j])
			continue;
		prime.push_back(j);
		for(int k = j*j;k<maxn;k += j){
			isPrime[k] = false;
		}
	}
}

int main(){
	vector<int>prime;
	int n;
	initial(prime);
	while(scanf("%d",&n) != EOF){
		int anwser = 0;
		for(int i = 0;i<prime.size() && prime[i] < n;i++)
		{
			int factor = prime[i];
			while(n%factor == 0){
				n /= factor;
				anwser++;
			}
		}
		if(n != 1)
			anwser++;

		printf("%d\n",anwser);
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48