用C++编写的素数判定程序

一、常见的素数判定算法

素数判定是数论中的基础问题，一般常用的算法有：试除法、埃氏筛、线性筛等。

试除法：对于一个数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++的素数判定程序实例。对于初学者来说，这些知识是入门必备的。通过学习这些算法和语法，可以让我们更好地理解程序设计的本质并提高代码的效率。