质数表的建法在上两个挑战中已经练习过了,那么剩下的问题就是,需要多大的质数表呢?
这时候需要考虑的是最坏情况,假设987654321是个质数,那么需要多少个小质数来试除才能判断出来?
这又转化到了一个熟悉的问题,判断质数试除到√n就够了,如果a * b = n 且 b > √n,那么必然有a < √n,a前面已经验证过了。
#include <stdio.h>
#include <math.h>
char buf[31427+1];
int prime_table[5000];
int main()
{
int i, j;
int pos = 0;
int upper = sqrt(31427);