@songpfei
2016-05-17T20:03:31.000000Z
字数 1210
阅读 1652
OJ_算法
素数判断方法:
原理:一个数 n 如果是合数,那么它的所有的因子不超过sqrt(n)--n的开方;
方案:使用循环解决;
时间复杂度:o(n*sqrt(n))
当n很大时很耗时;
void PrimeNumber(int n, int* primer, int& primer_num)
{
primer_num = 0;
int sqrt_i, i, j;
for (i = 2; i <= n; i++)
{
sqrt_i = (int)sqrt(i);
for (j = 2; j <= sqrt_i; j++)
if (i%j == 0)
break;
if (j > sqrt_i)
primer[primer_num++] = i;
}
}
此方法也有局限性,数据量中等时才不会超时,数据量过大时也会超时,而且只能用素数打表,不能对单个数进行判定!
void PrimeNumber(int n, int* primer, int& primer_num)
{
if (n < 2)
{
primer_num = 0;
return;
}
primer[0] = 2;
primer_num = 1;
for (int i = 1; i < n / 2 + 1; i++)
primer[i] = true;
for (int i = 1; i < n / 2 + 1; i++)
{
if (primer[i] && (2 * i + 1) <= n)
{
primer[primer_num++] = 2 * i + 1;
for (int j = 3 * i + 1; j < n / 2 + 1; j = j + 2 * i + 1)
primer[j] = false;
}
}
}
bool IsPrimerNum(int n, int* primer, int&primer_num)
{
int sqrt_i= (int)sqrt(n);
for (int i = 0; primer[i] <= sqrt_i&&primer_num; i++)
{
if (n%primer[i] == 0)
return 0;
}
return 1;
}
void PrimeNumber(int n, int* primer, int& primer_num)
{
primer_num = 0;
for (int i = 2; i <= n; i++)
if (IsPrimerNum(i, primer, primer_num))
primer[primer_num++] = i;
}
参考:http://blog.csdn.net/liukehua123/article/details/5482854
参考:大神http://blog.csdn.net/arvonzhang/article/details/8564836