用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