一、常见的素数判定算法
素数判定是数论中的基础问题，一般常用的算法有：试除法、埃氏筛、线性筛等。
试除法：对于一个数n，从2开始只要能整除n，n就不是素数。
比如259，因为能被7整除，所以不是素数。
这个算法简单，容易实现，但是当n很大时，需要进行很多次除法操作，效率比较低。
埃氏筛：将从2开始的所有自然数入列，取出队首的数p，将p的倍数依次排除，直到队列为空，则不在这个过程中被筛去的数便是素数。
比如100以内的素数：2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97。
线性筛：试除法的时间复杂度为O($\sqrt n$)，埃氏筛的时间复杂度为O(nloglogn)，而线性筛法的时间复杂度为O(n)。其基本思想是：
如果x是质数，那么x的倍数一定不是质数；如果x不是质数，那么x一定是之前某个质数的倍数，它已经在这个质数的筛法中被标记过了。
void get_prime(int n) {
memset(v, 0, sizeof(v));
memset(prime, 0, sizeof(prime));
int cnt = 0;
for(int i = 2; i <= n; i++) {
if(v[i] == 0) {
prime[cnt] = i;
cnt++;
}
for(int j = 0; j < cnt && i * prime[j] <= n; j++) {
v[i * prime[j]] = 1;
if(i % prime[j] == 0) break;
}
}
}
二、C++的相关语法
C++是一种高级的程序设计语言，它结合了高级语言和低级语言的优点，可以进行高效的系统级编程和高级应用程序开发。下面介绍一些C++常用的语法。
1. 变量：变量是用于存储值的内存位置。在C++中，变量必须在使用之前被声明。变量的声明语法：类型 变量名;
2. if语句：if语句用于在程序中执行不同的动作，根据条件执行不同的代码块。if语句的语法：
if(condition) {
// code if condition is true
}
3. for循环：for循环是一种循环结构，可以重复执行一定的代码，直到达到指定的次数。for循环的语法：
for(initialization; condition; updation) {
// code
}
4. 函数：函数是一种独立的代码块，可以被多次调用。在C++中，函数的声明必须在使用之前。函数的语法：
type function_name(type parameter1, type parameter2,...) {
// code
return value;
}
三、基于C++的素数判定程序实例
下面是一个基于C++的素数判定程序实例。这个程序使用了线性筛法来判定素数。
#include
using namespace std;
const int MAXN = 1000000;
int prime[MAXN], v[MAXN], cnt;
void get_prime(int n) {
memset(v, 0, sizeof(v));
memset(prime, 0, sizeof(prime));
cnt = 0;
for(int i = 2; i <= n; i++) {
if(v[i] == 0) {
prime[cnt] = i;
cnt++;
}
for(int j = 0; j < cnt && i * prime[j] <= n; j++) {
v[i * prime[j]] = 1;
if(i % prime[j] == 0) break;
}
}
}
bool is_prime(int n) {
if(n < 2) return false;
for(int i = 2; i * i <= n; i++) {
if(n % i == 0) return false;
}
return true;
}
int main() {
int x = 37;
if(is_prime(x)) {
cout << x << " is a prime number." << endl;
} else {
cout << x << " is not a prime number." << endl;
}
get_prime(100);
for(int i = 0; i < cnt; i++) {
cout << prime[i] << " ";
}
cout << endl;
return 0;
}
四、总结
本文主要介绍了素数判定的常见算法，包括试除法、埃氏筛和线性筛法。同时，也介绍了C++的一些基本语法以及一个基于C++的素数判定程序实例。对于初学者来说，这些知识是入门必备的。通过学习这些算法和语法，可以让我们更好地理解程序设计的本质并提高代码的效率。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/286711.html
微信扫一扫 
支付宝扫一扫 