C++质数的寻找和判断方式(代码)_找质数c++

需要找出小于某个值的所有质数时

根据质数的定义，可以知道，如果一个数所有小于他的质数都不是他的因数，那么他就是质数

#include<iostream>
#include<vector>
using namespace std;

//key是要判断的数字，a是vector类的元素，其中保存了所有比key小的质数
bool check(int key,vector<int>& a) {
	for (int i = 0; i < a.size(); i++) {
		if (key % a[i] == 0) {
			return false;
		}
	}
	return true;
}

int main() {
	vector<int> zhishu;
	zhishu.push_back(2);
	int max;//输入的上界
	cin >> max;
	if (max < 2) {
		cout << "无";
	}
	else if (max == 2) {
		cout << 2 << "\n";//输出唯一的质数2
	}
	else {
		for (int i = 3; i < max; i+=2) {//每次加2，因为只有奇数才可能是素数
			if (check(i, zhishu)) {
				zhishu.push_back(i);
			}
		}
	}
	for(int i=0;i<zhishu.size();i++){
	cout<<zhishu[i];
	}
	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

只判断单一数字是否为质数

#include<math.h>
 bool IsPrime(int x)
{
    if (1 == x)
    {
        cout << "1既不是质数也不是合数！" << endl;
        return false;
    }
    for (int i = 2; i <= sqrt(x); i++)
        if (x%i == 0)
        {
            return false;
        }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15