素数求解问题及优化
1描述
素数求解问题在程序员的面试中是个很简单的问题，经常是小公司的基础面试题。然而因为一些个小紧张什么的，弄跪了些许人
那么，今天就关于这个问题我们来进行总结及方案优化
素数概念:除了1和它本身不能被其他数整除的数字都是素数
我们就围绕 bool IsPrime(int n) 判断一个数是否为素数来谈吧
2实现
①依据概念实现
bool IsPrime(int n)
{
if(n < 2)
return false;
for(int i = 2;i<n;++i)
{
if(n%i==0)
reurn false;
}
return true;
}
②优化一：因为偶数必然不为素数，所以i+=2;
bool IsPrime(int n)
{
if(n < 2)
return false;
if(n == 2)
return true;
for(int i = 3; i < n;i+=2)
{
if(n%i==0)
return false;
}
return true;
}
优化二：eg 对于100;大于50的数字必然不能整除100；所以i<n/2;
优化三：对于数字M，要确定一个整除它的数字k，会有k1*K2==M，那么，K1，K2如何才能最小呢，那就是K1==K2，所以优化为i*i<n;
bool IsPrime(int n)
{
if(n<2)
return false;
for(int i =2;i*i < n;++i)
{
if(n%i==0)
return false;
}
return true;
}
优化四：素数表方案求解
分析：
对于一个合数，进行因式分解，最终得到的会是一些个质数只积，那么就有如果一个数无法被比他小的质数整除，那么他本身也是素数
所以就有素数表方案求解素数问题的提出。关于M以内质数个数的估算结果是：
//int nMaxLen=static_cast<int> ((n/log(double(n)))*1.5);
void PrintPrimeInN(int n)
{
int nMaxLen=static_cast<int> ((n/log(double(n)))*1.5);
int *arr = new int[nMaxLen];
int count = 0;
arr[count++] = 2;
for(int i = 2;i<=n;++i)
{
int flag = true;
for(int j =0;arr[j]*arr[j] < i;++j)
{
if(i%arr[j] == 0)
{
flag = false;
break;
}
}
if(flag)
arr[count++] = i;
}
}
以上就是关于素数求解的全过程及优化。