[数据结构与算法]洛谷 P5736 质数筛 题解

题目描述

输入n(n≤100) 个不大于 100000 的整数。要求全部储存在数组中，去除掉不是质数的数字，依次输出剩余的质数。

题目分析

质数又称素数。所谓素数是指除了 1 和它本身以外，不能被任何整数整除的数，例如17就是素数，因为它不能被 2~16 的任一整数整除。
创建数组存放数据，如果这个数m求余从2到根号m中没有等于0的数，则这个数位素数。（因为如果 m 能被 2 ~ m-1 之间任一整数整除，其二个因子必定有一个小于或等于根号m ，另一个大于或等于根号m ）

代码如下

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
	int a[101],n,i,j,c;
	cin>>n;
	
	for(i=0;i<n;i++)
	cin>>a[i];
	for(i=0;i<n;i++)
	{
		c=0;
		if(a[i]==1)   //1不是素数
		continue;
		for(j=2;j<=pow(a[i],0.5);j++)
		{
			if(a[i]%j==0)
			c+=1;
		}
		if(c==0)    //c=0表示没有数可以整除，这个数为素数
		cout<<a[i]<<" ";
	}

 }