质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）。
一、直接暴力法求素数
n的素数的判断，我自己只想到了把2到n-1，实际上你要判断到n/2,任何合数最小的因子就是2，那最大的因子就是 n/2，再进一步其实sqrt（n）就够了。
bool prime_number(int a)
{
int i = 0;
for(i = 2;i<=(int)sqrt(a);i++)
{
if(a%i == 0)
{
return false;
}
}
return true;
}
二、筛选法求素数
用筛选法求n以内的素数。筛选法求解过程为：将2~n之间的正整数放在数组内存储，将数组中2之后的所有能被2整除的数清0，再将3之后的所有能被3整除的数清0 ，以此类推，直到n为止。数组中不为0 的数即为素数。
#include <stdio.h>
int main()
{
int n =0;
scanf("%d",&n);
int arr[100] = {
0};
int i = 0;
for(i = 2;i<=n;i++)
{
arr[i-2] = i;
}
int count = 0;
for(i = 2; i < n; i++)
{
int j = 0;
for(j = i+1;j<=n;j++)
{
if(arr[j-2]%i == 0)
{
arr[j-2] = 0;
}
}
}
for(i = 2;i<=n;i++)
{
if(arr[i-2] != 0)
printf("%d ",arr[i-2]);
else
count++;
}
printf("\n");
printf("%d",count);
return 0;
}
三、用素数表来判断素数
如果一个数不能整除比它小的任何素数，那么这个数就是素数
//target：输入的要查找的数
//count：当前已知的素数个数
//PrimeArray：存放素数的数组
int isPrime(int target, int count, int* PrimeArray) {
int i = 0;
for (i = 0; i < count; i++) {
if (target % PrimeArray[i] == 0)
return 0;
}
return 1;
}
素数拓展：素数回文
回文既对称的意思，比如一个数字12321，以3为中点对称，如何判断一个素数的回文数字是否是素数呢，我们可以先求出这个素数的回文，再去判断
bool prime_number(long long a)
{
long long i = 0;
for(i = 2;i<=(long long )sqrt(a);i++)
{
if(a%i == 0)
{
return false;
}
}
return true;
}
long long huiwen(long long a)
{
long long tmp =a;
while(tmp /= 10)
{
a = a*10+ tmp%10;
}
return a;
}
