一般方法

利用素数的定义进行遍历求解

bool prime(int n)//判断变量n是否为素数 
{
  for (int i = 2; i <= sqrt(n); i++)//范围到sqrt(n);
    if ((n % i) == 0) return false;//出现能够被整除的数字i返回false表示不为素数
  return true;//遍历完之后没有出现能够被整除的返回ture表示为素数
}
//该方法适用于计算单个或少量素数(素数不会过大)；

埃氏筛法

利用素数的n倍( n>=2)不为素数可以筛掉素数

原理图：

通过原理图不难看出埃氏筛法依旧有不足之处,譬如通过2 x 3和3 x 2会对6筛掉两次，这样就会出现一个数被筛多次,但是用于普通算法比赛这个时间复杂度(O(nlong(log n))完全够用了如果依旧超时可以去查看欧拉筛法

C++代码实现(部分代码)

const int maxn=40000;//定义为全局变量
long prime[maxn];
bool is_prime[maxn+1]; 
int p = 0;
void primes(int n)
{
 	p = 0;
	for(int i=0;i<=n;i++)
		is_prime[i]=true;//初始化bool数组ture标志为素数    
    is_prime[0] = is_prime[1] = false; //将0，1标准为非素数
    for(int i=2;i<=n;i++)
    {
       	if(is_prime[i])//如果i为素数则执行循环         
    	{
             prime[p++]=i;//将素数记录进数组    
             for(int j=i*i;j<=n;j+=i) 
    				is_prime[j]=false;//将i的n倍标记为非素数
        }
    }
    return ;   
}

上述代码可以直接使用使用方法为primes(40000);数据范围可以手动修改修改maxn即可修改最大数据范围

END

Q.E.D.