素数的判断

5.4.1 素数的判断

• 存在整数a（判断其是否为素数）
• 如果存在一个正整数b可以整除素数a，即b是a的约数，那么必定存在另一个数c，使得bc = a
• 当b==c时，它们的值为,如果它们的值不想等，那么必定一个大于，另一个小于。
• 所以我们只需要判断a是否可以被的下取整整除

bool isPrim(int num) {
    if(num < 1) {
        return false;
    }
    // n没有接近上界的时候才可以这样写，否则很容易越界。后者吧i的类型改为long long
    for(int i = 2; i*i < num; i++) {
        if(num % i == 0) return false;
    }
    return true;
}

5.4.2 素数表的获取

• 如果要获取从1～n的素数，通过上面的方法则时间复杂度为,这个对n不超过100000时没问题的

const int MAX_LEN = 101;
int primes[MAX_LEN] = {0};
bool p[MAX_LEN] = {0}; // p[i] == true表示它是素数
int nPrimes = 0;
void findPrimes() {
    for(int i = 1; i < MAX_LEN; i++) {
        if(isPrim(i)) {
            p[i] = true;
            primes[nPrims++] = i;
        }
    }
}

• 但是如果出现需要更大范围的素数表，上述算法将力不从心。
• 下面学习一种筛法，时间复杂度为

• 算法从小到大枚举所有数，对每一个数，筛去它所有的倍数，剩下的就都是素数了。

  
  image.png

• why？-如果a不是素数，那么一定有小于a的素因子，这样在之前的步骤中a一定会被筛掉。
• how？-筛这个动作的实现，可以使用一个bool型数组p来标记，如果a被筛掉，那么p[a]=true;否则为false。程序开始前，数组初始化成false。

#include <iostream>
using namespace std;

const int MAX_LEN = 101;
int primes[MAX_LEN], nPrimes= 0;
bool p[MAX_LEN] = {0};

void find_primes() {
    for(int i = 2; i < MAX_LEN; i++) {
        if(!p[i]) {
            primes[nPrimes++] = i;
            for(int j = i*2; j < MAX_LEN; j += i) {
                p[j] = true;
            }
        }
    }
}

int main() {
    find_primes();
}

习题

• 素数
  • 注意点：输出格式存在坑，最后一个素数指的是所有素数中的最后一个，而不是末尾为1的素数的最后一个。

#include <cstdio>
const int maxn=10001;
int prime[maxn],num=0;
bool p[maxn]={0};
void Find_Prime()
{
    for(int i=2;i<maxn;i++)
    {
        if(p[i]==false)
        {
            prime[num++]=i;
            for(int j=i+i;j<maxn;j+=i)
                p[j]=true;
        }
    }
}
int main()
{
    int n;
    Find_Prime();
    while(~scanf("%d",&n))
    {
        int count=0;
        for(int i=0;i<maxn;i++)
        {
            if(prime[i]<n&&prime[i]%10==1)
            {
                count++;
                printf("%d",prime[i]);
                if(i!=num-1){
                    printf("(%d, %d)", i, num-1);
                    printf("*");
                }
            }
            else if(prime[i]>=n)
                break;
        }
        if(count==0)    printf("-1");
        printf("\n");
    }
    return 0;
}

• 问题 B: Prime Number
  • 注意点：用于存储素数的数组容量必须很大，因为要查询第10000个素数，它的值大于10w

#include <iostream>
using namespace std;

const int MAX_LEN = 200001;
int primes[MAX_LEN], nPrimes= 0;
bool p[MAX_LEN] = {0};

void find_primes() {
    nPrimes = 0;
    for(int i = 2; i < MAX_LEN; i++) {
        //if(i > n) break;
        if(!p[i]) {
            primes[nPrimes++] = i;
            for(int j = i*2; j < MAX_LEN; j += i) {
                p[j] = true;
            }
            
        }
    }
}

int main() {
    int n;
    find_primes();
    while(scanf("%d", &n) != EOF) {
        printf("%d\n", primes[n-1]);
    }
    
    return 0;
}

• 问题 C: Goldbach's Conjecture

#include <iostream>
using namespace std;

const int MAX_LEN = 40000; // 2^15是32768
int primes[MAX_LEN];
int cnt = 0;
bool p[MAX_LEN] = {0};

void find_primes() {
    for(int i = 2; i < MAX_LEN; i++) {
        // 如果没有被筛掉
        if(!p[i]) {
            primes[cnt++] = i;
            for(int j = i*2; j < MAX_LEN; j += i) {
                p[j] = true;
            }
        }
    }
}

int main()
{
    int n;
    find_primes();
    
    while(scanf("%d", &n) != EOF) {
        if(n == 0) break;
        int mid = n / 2;
        int res = 0;
        // 直接从素数表开始循环，素数表中存放的值为素数。
        for(int i = 0; i < cnt; i++) {
            // 重点是这里的下标别搞错了！！！
            if(primes[i] <= mid && !p[n-primes[i]]) {
                res++;
                //printf("(%d,%d)\n", primes[i], n-primes[i]);
            }
            else if(primes[i] > mid) break;
        }
        printf("%d\n", res);
    }   
    return 0;
}